結果

問題 No.2286 Join Hands
ユーザー 👑 rin204
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import deque
from dataclasses import dataclass
class mf_graph:
@dataclass
class edge:
from_: int
to: int
cap: int
flow: int
# def __init__(self, from_, to, cap, flow):
# self.from_ = from_
# self.to = to
# self.cap = cap
# self.flow = flow
@dataclass
class _edge:
to: int
rev: int
cap: int
# def __init__(self, to, rev, cap):
# self.to = to
# self.rev = rev
# self.cap = cap
def __init__(self, n):
self.n = n
self.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 += 1
self.G[from_].append(mf_graph._edge(to, to_id, cap))
self.G[to].append(mf_graph._edge(from_, from_id, 0))
return m
def 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 result
def 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_flow
self.G[self.pos[i][0]][self.pos[i][1]].cap = new_cap - new_flow
def flow(self, s, t, flow_limit=1 << 60):
level = []
iter = []
que = deque()
def bfs():
nonlocal level
level = [-1] * self.n
level[s] = 0
que.clear()
que.append(s)
while que:
v = que.popleft()
for e in self.G[v]:
if e.cap == 0 or level[e.to] >= 0:
continue
level[e.to] = level[v] + 1
if e.to == t:
return
que.append(e.to)
def dfs(v, up):
if v == s:
return up
nonlocal level, iter
res = 0
level_v = level[v]
while iter[v] < len(self.G[v]):
i = iter[v]
iter[v] += 1
e = self.G[v][i]
if level_v <= level[e.to] or self.G[e.to][e.rev].cap == 0:
continue
d = dfs(e.to, min(up - res, self.G[e.to][e.rev].cap))
if d <= 0:
continue
self.G[v][i].cap += d
self.G[e.to][e.rev].cap -= d
res += d
if res == up:
return res
level[v] = self.n
return res
flow = 0
while flow < flow_limit:
bfs()
if level[t] == -1:
break
iter = [0] * self.n
f = dfs(t, flow_limit - flow)
if f == 0:
break
flow += f
return flow
def min_cut(self, s):
visited = [False] * self.n
que = deque()
que.append(s)
while que:
p = que.popleft()
visited[p] = True
for e in self.G[p]:
if e.cap and not visited[e.to]:
visited[e.to] = True
que.append(e.to)
return visited
n, m = map(int, input().split())
G = mf_graph(2 * n + 2)
s = 2 * n
t = s + 1
for 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 -= 1
v -= 1
G.add_edge(u, n + v, 1)
G.add_edge(v, n + u, 1)
res = G.flow(s, t)
if res == n - 1:
res = n - 2
ans = res - (n - res)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0