結果
問題 | No.119 旅行のツアーの問題 |
ユーザー | cologne |
提出日時 | 2022-02-08 22:39:44 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 43 ms / 5,000 ms |
コード長 | 3,045 bytes |
コンパイル時間 | 117 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-06-23 18:28:11 |
合計ジャッジ時間 | 1,837 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
11,776 KB |
testcase_01 | AC | 42 ms
11,904 KB |
testcase_02 | AC | 38 ms
11,776 KB |
testcase_03 | AC | 37 ms
11,648 KB |
testcase_04 | AC | 37 ms
11,648 KB |
testcase_05 | AC | 39 ms
11,776 KB |
testcase_06 | AC | 40 ms
11,776 KB |
testcase_07 | AC | 36 ms
11,648 KB |
testcase_08 | AC | 37 ms
11,776 KB |
testcase_09 | AC | 37 ms
11,776 KB |
testcase_10 | AC | 36 ms
11,648 KB |
testcase_11 | AC | 38 ms
11,776 KB |
testcase_12 | AC | 37 ms
11,904 KB |
testcase_13 | AC | 38 ms
11,776 KB |
testcase_14 | AC | 37 ms
11,904 KB |
testcase_15 | AC | 37 ms
11,776 KB |
testcase_16 | AC | 42 ms
12,160 KB |
testcase_17 | AC | 38 ms
11,776 KB |
testcase_18 | AC | 38 ms
11,648 KB |
testcase_19 | AC | 38 ms
11,776 KB |
testcase_20 | AC | 39 ms
11,904 KB |
testcase_21 | AC | 41 ms
12,032 KB |
testcase_22 | AC | 42 ms
12,160 KB |
ソースコード
from collections import deque from math import inf from typing import List, Tuple, Union import sys sys.setrecursionlimit(10**6) class MaxFlow: 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 = [to, None, capacity] to_edge = [from_, from_edge, 0] from_edge[1] = 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]: to, _, cap = edg if cap > 0 and level[to] == -1: level[to] = level[u] + 1 if to == sink: return True Q.append(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]] to, rev, cap = edg if cap <= 0 or level[to] <= level[e]: cnt[e] += 1 continue flowed = flow(to, min(f, cap)) if flowed > 0: edg[2] -= flowed rev[2] += 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()