結果
問題 | No.119 旅行のツアーの問題 |
ユーザー | cologne |
提出日時 | 2022-02-08 22:37:45 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 60 ms / 5,000 ms |
コード長 | 3,180 bytes |
コンパイル時間 | 104 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2024-06-23 18:26:27 |
合計ジャッジ時間 | 2,361 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
13,312 KB |
testcase_01 | AC | 55 ms
13,312 KB |
testcase_02 | AC | 53 ms
13,056 KB |
testcase_03 | AC | 53 ms
13,184 KB |
testcase_04 | AC | 55 ms
13,312 KB |
testcase_05 | AC | 56 ms
13,440 KB |
testcase_06 | AC | 59 ms
13,312 KB |
testcase_07 | AC | 56 ms
13,184 KB |
testcase_08 | AC | 56 ms
13,312 KB |
testcase_09 | AC | 57 ms
13,056 KB |
testcase_10 | AC | 54 ms
13,184 KB |
testcase_11 | AC | 55 ms
13,184 KB |
testcase_12 | AC | 55 ms
13,184 KB |
testcase_13 | AC | 54 ms
13,184 KB |
testcase_14 | AC | 53 ms
13,184 KB |
testcase_15 | AC | 56 ms
13,312 KB |
testcase_16 | AC | 58 ms
13,440 KB |
testcase_17 | AC | 54 ms
13,184 KB |
testcase_18 | AC | 56 ms
13,056 KB |
testcase_19 | AC | 54 ms
13,056 KB |
testcase_20 | AC | 56 ms
13,312 KB |
testcase_21 | AC | 57 ms
13,440 KB |
testcase_22 | AC | 60 ms
13,568 KB |
ソースコード
from collections import deque from math import inf from typing import List, Tuple, Union from dataclasses import dataclass import sys sys.setrecursionlimit(10**6) class MaxFlow: @dataclass class Edge: to: int rev: 'MaxFlow.Edge' cap: Union[int, float] def __init__(self, N: int): self.__N: int = N self.__G: List[List[MaxFlow.Edge]] = [[] for _ in range(N)] self.__E: List[Tuple[MaxFlow.Edge, MaxFlow.Edge]] = [] def add_edge(self, from_: int, to: int, capacity: Union[int, float]): assert 0 <= from_ < self.__N assert 0 <= to < self.__N assert 0 <= capacity from_edge = MaxFlow.Edge(to, None, capacity) to_edge = MaxFlow.Edge(from_, from_edge, 0) from_edge.rev = to_edge self.__E.append((from_edge, to_edge)) self.__G[from_].append(from_edge) self.__G[to].append(to_edge) return len(self.__E) - 1 def flow(self, source: int, sink: int, flow_limit: Union[int, float] = inf): assert 0 <= source < self.__N assert 0 <= sink < self.__N assert source != sink assert flow_limit >= 0 level: List[int] = [] cnt: List[int] = [] def bfs(): level[source] = 0 Q = deque([source]) while len(Q) != 0: u = Q.popleft() for edg in self.__G[u]: if edg.cap > 0 and level[edg.to] == -1: level[edg.to] = level[u] + 1 if edg.to == sink: return True Q.append(edg.to) return False def flow(e, f): if e == sink: return f while cnt[e] < len(self.__G[e]): edg = self.__G[e][cnt[e]] if edg.cap <= 0 or level[edg.to] <= level[e]: cnt[e] += 1 continue flowed = flow(edg.to, min(f, edg.cap)) if flowed > 0: edg.cap -= flowed edg.rev.cap += flowed return flowed level[e] = -1 return 0 answer = 0 while flow_limit > 0: level = [-1] * self.__N cnt = [0] * self.__N if not bfs(): break while True: flowed = flow(source, flow_limit) if flowed <= 0: break answer += flowed flow_limit -= flowed return answer def main(): N = int(input()) BC = [tuple(map(int, input().split())) for i in range(N)] M = int(input()) DE = [tuple(map(int, input().split())) for i in range(M)] G = MaxFlow(2*N+2) ans = 0 for i in range(N): B, C = BC[i] ans += max(B, C) G.add_edge(2*N, 2*i, max(B, C) - C) G.add_edge(2*i, 2*i+1, max(B, C)) G.add_edge(2*i+1, 2*N+1, max(B, C) - B) for d, e in DE: G.add_edge(2*d+1, 2*e, inf) ans -= G.flow(2*N, 2*N+1) print(ans) if __name__ == '__main__': main()