結果
問題 | No.2320 Game World for PvP |
ユーザー |
|
提出日時 | 2023-02-26 04:41:18 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,419 bytes |
コンパイル時間 | 534 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 92,928 KB |
最終ジャッジ日時 | 2024-10-11 04:56:05 |
合計ジャッジ時間 | 8,813 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 4 |
other | WA * 30 |
ソースコード
import sys from collections import deque, Counter from math import gcd, log10, pi, sqrt, ceil from bisect import bisect, bisect_left, bisect_right, insort from typing import Iterable, TypeVar, Union, Tuple, Iterator, List import copy import heapq import itertools import math import random from fractions import Fraction from functools import lru_cache, partial, cmp_to_key import operator input = sys.stdin.readline sys.setrecursionlimit(10000000) mod = 998244353 INF = 1 << 61 DIFF = 10 ** -9 DX = [1, 0, -1, 0, 1, 1, -1, -1] DY = [0, 1, 0, -1, 1, -1, 1, -1] def read_values(): return map(int, input().split()) def read_index(): return map(lambda x: int(x) - 1, input().split()) def read_list(): return list(read_values()) def read_lists(N): return [read_list() for _ in range(N)] class Flow: def __init__(self, V): self.V = V self.G = [dict() for _ in range(V)] def add_edge(self, u, v, cap): self.G[u][v] = self.G[u].get(v, 0) + cap if u not in self.G[v]: self.G[v][u] = 0 def add_multi_edge(self, u, v, cap1, cap2): self.G[u][v] = self.G[u].get(v, 0) + cap1 self.G[v][u] = self.G[v].get(u, 0) + cap2 def wfs(self, s, g): S = [(s, -1, INF)] P = [-1] * self.V while S: u, p, f = S.pop() if u == g: break for v, c in self.G[u].items(): if c <= 0: continue if P[v] != -1: continue t = min(f, c) P[v] = u S.append((v, u, t)) else: return 0 while u != s: p = P[u] self.G[p][u] -= f self.G[u][p] += f u = p return f def flow(self, s, g): res = 0 r = self.wfs(s, g) while r > 0: res += r r = self.wfs(s, g) return res def main(): N, S, T = read_values() A = list(read_index()) B = list(read_index()) C = read_lists(N) flow = Flow(N + 2) for i in A: flow.add_edge(0, i + 1, INF) for i in B: flow.add_edge(i + 1, N + 1, INF) for i in range(N): for j in range(i + 1, N): flow.add_multi_edge(i + 1, j + 1, C[i][j], C[i][j]) print(flow.flow(0, N + 1)) if __name__ == "__main__": main()