結果
問題 | No.2286 Join Hands |
ユーザー |
👑 |
提出日時 | 2024-04-29 21:45:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,993 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 92,776 KB |
最終ジャッジ日時 | 2024-11-19 05:58:20 |
合計ジャッジ時間 | 11,825 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 WA * 9 RE * 2 |
ソースコード
from collections import dequefrom dataclasses import dataclassclass mf_graph:@dataclassclass edge:from_: intto: intcap: intflow: int# def __init__(self, from_, to, cap, flow):# self.from_ = from_# self.to = to# self.cap = cap# self.flow = flow@dataclassclass _edge:to: intrev: intcap: int# def __init__(self, to, rev, cap):# self.to = to# self.rev = rev# self.cap = capdef __init__(self, n):self.n = nself.G = [[] for _ in range(n)]self.pos = []def add_edge(self, from_, to, cap):m = len(self.pos)self.pos.append((from_, len(self.G[from_])))from_id = len(self.G[from_])to_id = len(self.G[to])if from_ == to:to_id += 1self.G[from_].append(mf_graph._edge(to, to_id, cap))self.G[to].append(mf_graph._edge(from_, from_id, 0))return mdef get_edge(self, i):_e = self.G[self.pos[i][0]][self.pos[i][1]]_re = self.G[_e.to][_e.rev]return mf_graph.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)def edges(self):m = len(self.pos)result = []for i in range(m):result.append(self.get_edge(i))return resultdef change_edge(self, i, new_cap, new_flow):_e = self.G[self.pos[i][0]][self.pos[i][1]]self.G[_e.to][_e.rev].cap = new_flowself.G[self.pos[i][0]][self.pos[i][1]].cap = new_cap - new_flowdef flow(self, s, t, flow_limit=1 << 60):level = []iter = []que = deque()def bfs():nonlocal levellevel = [-1] * self.nlevel[s] = 0que.clear()que.append(s)while que:v = que.popleft()for e in self.G[v]:if e.cap == 0 or level[e.to] >= 0:continuelevel[e.to] = level[v] + 1if e.to == t:returnque.append(e.to)def dfs(v, up):if v == s:return upnonlocal level, iterres = 0level_v = level[v]while iter[v] < len(self.G[v]):i = iter[v]iter[v] += 1e = self.G[v][i]if level_v <= level[e.to] or self.G[e.to][e.rev].cap == 0:continued = dfs(e.to, min(up - res, self.G[e.to][e.rev].cap))if d <= 0:continueself.G[v][i].cap += dself.G[e.to][e.rev].cap -= dres += dif res == up:return reslevel[v] = self.nreturn resflow = 0while flow < flow_limit:bfs()if level[t] == -1:breakiter = [0] * self.nf = dfs(t, flow_limit - flow)if f == 0:breakflow += freturn flowdef min_cut(self, s):visited = [False] * self.nque = deque()que.append(s)while que:p = que.popleft()visited[p] = Truefor e in self.G[p]:if e.cap and not visited[e.to]:visited[e.to] = Trueque.append(e.to)return visitedn, m = map(int, input().split())G = mf_graph(2 * n + 2)s = 2 * nt = s + 1for i in range(n):G.add_edge(s, i, 1)G.add_edge(n + i, t, 1)for i in range(m):u, v = map(int, input().split())u -= 1v -= 1G.add_edge(u, n + v, 1)G.add_edge(v, n + u, 1)res = G.flow(s, t)if res == n - 1:res = n - 2ans = res - (n - res)print(ans)