結果
| 問題 | No.3668 Minimum Cut |
| コンテスト | |
| ユーザー |
 tyuyu_62
|
| 提出日時 | 2026-09-04 22:51:35 |
| 言語 | PyPy3 (7.3.23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,674 bytes |
| 記録 | |
| コンパイル時間 | 425 ms |
| コンパイル使用メモリ | 95,952 KB |
| 実行使用メモリ | 90,072 KB |
| 最終ジャッジ日時 | 2026-09-04 23:02:27 |
| 合計ジャッジ時間 | 8,462 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 TLE * 1 -- * 17 |
ソースコード
# https://github.com/tyuyu-62/cp-library
from collections import deque, defaultdict
from itertools import permutations, product
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from random import randint, shuffle
from time import perf_counter as pc
def II(): return int(input())
def LI(dec=0): return [int(x) - dec for x in input().split()]
def SI(): return input()
def LS(): return list(input().split())
mod = 998244353
inf = 2002002002002002002
import sys
sys.setrecursionlimit(10 ** 6)
input = lambda: sys.stdin.readline().rstrip()
_buf = []
def print(*args, sep=" "): _buf.append(sep.join(map(str, args)))
def debug(*args):
if DEBUG: sys.stdout.write(" ".join(map(str, args)) + "\n")
DEBUG = True
# https://github.com/tyuyu-62/cp-library
INF = 2002002002002002002
class MaxFlow:
"""Dinic maximum flow with an iterative blocking-flow search.
Args:
N: Number of vertices.
Constraints:
0 <= N.
Capacities are nonnegative integers.
Source and sink are different.
The answer and flow_limit are at most INF.
Time:
O(V^2 E) for ``flow`` in general.
Space:
O(V + E).
"""
__slots__ = (
"_N",
"_graph",
"_to",
"_capacity",
"_position",
"_level",
"_iterator",
"_queue",
"_stack_vertex",
"_stack_edge",
"_stack_flow",
)
def __init__(self, N: int) -> None:
"""Initialize an empty N-vertex flow graph.
Time:
O(N).
"""
self._N = N
self._graph = [[] for _ in range(N)]
self._to = []
self._capacity = []
self._position = []
self._level = [-1] * N
self._iterator = [0] * N
self._queue = [0] * N
self._stack_vertex = [0] * (N + 1)
self._stack_edge = [0] * N
self._stack_flow = [0] * (N + 1)
def add_edge(self, from_: int, to: int, capacity: int) -> int:
"""Add a directed capacitated edge and return its edge ID.
Time:
Amortized O(1).
"""
edge = len(self._to)
edge_id = len(self._position)
self._position.append(edge)
self._to.append(to)
self._capacity.append(capacity)
self._to.append(from_)
self._capacity.append(0)
self._graph[from_].append(edge)
self._graph[to].append(edge + 1)
return edge_id
def flow(
self,
source: int,
sink: int,
flow_limit: int = INF,
) -> int:
"""Send at most flow_limit additional flow.
The residual graph is retained, so subsequent calls send
additional flow.
Time:
O(V^2 E) in general.
"""
N = self._N
graph = self._graph
to = self._to
capacity = self._capacity
level = self._level
iterator = self._iterator
queue = self._queue
stack_vertex = self._stack_vertex
stack_edge = self._stack_edge
stack_flow = self._stack_flow
total = 0
while total < flow_limit:
v = 0
while v < N:
level[v] = -1
v += 1
level[source] = 0
queue[0] = source
left = 0
right = 1
while left < right:
v = queue[left]
left += 1
next_level = level[v] + 1
edges = graph[v]
i = 0
end = len(edges)
while i < end:
edge = edges[i]
u = to[edge]
if capacity[edge] and level[u] == -1:
level[u] = next_level
queue[right] = u
right += 1
i += 1
if level[sink] == -1:
break
v = 0
while v < N:
iterator[v] = 0
v += 1
while total < flow_limit:
stack_vertex[0] = source
stack_flow[0] = flow_limit - total
size = 1
pushed = 0
while size:
v = stack_vertex[size - 1]
if v == sink:
pushed = stack_flow[size - 1]
i = 0
while i + 1 < size:
edge = stack_edge[i]
capacity[edge] -= pushed
capacity[edge ^ 1] += pushed
i += 1
break
edges = graph[v]
i = iterator[v]
end = len(edges)
next_level = level[v] + 1
while i < end:
edge = edges[i]
if (
capacity[edge]
and level[to[edge]] == next_level
):
break
i += 1
iterator[v] = i
if i == end:
level[v] = -1
size -= 1
if size:
iterator[stack_vertex[size - 1]] += 1
continue
edge = edges[i]
u = to[edge]
stack_edge[size - 1] = edge
stack_vertex[size] = u
value = stack_flow[size - 1]
edge_capacity = capacity[edge]
stack_flow[size] = (
edge_capacity
if edge_capacity < value
else value
)
size += 1
if pushed == 0:
break
total += pushed
return total
def max_flow(
self,
source: int,
sink: int,
flow_limit: int = INF,
) -> int:
"""Send at most flow_limit additional flow.
This is an alias of ``flow``.
Time:
O(V^2 E) in general.
"""
return self.flow(source, sink, flow_limit)
def get_edge(self, edge_id: int) -> tuple:
"""Return (from, to, capacity, flow) for an edge.
Time:
O(1).
"""
edge = self._position[edge_id]
capacity = self._capacity
flow = capacity[edge ^ 1]
return (
self._to[edge ^ 1],
self._to[edge],
capacity[edge] + flow,
flow,
)
def edges(self) -> list[tuple]:
"""Return all edges as (from, to, capacity, flow).
Time:
O(E).
"""
position = self._position
to = self._to
capacity = self._capacity
result = [None] * len(position)
i = 0
while i < len(position):
edge = position[i]
flow = capacity[edge ^ 1]
result[i] = (
to[edge ^ 1],
to[edge],
capacity[edge] + flow,
flow,
)
i += 1
return result
def change_edge(
self,
edge_id: int,
new_capacity: int,
new_flow: int,
) -> None:
"""Set an edge's capacity and current flow.
Constraints:
0 <= new_flow <= new_capacity.
Time:
O(1).
"""
edge = self._position[edge_id]
self._capacity[edge] = new_capacity - new_flow
self._capacity[edge ^ 1] = new_flow
def clear_flow(self) -> None:
"""Set every edge flow to zero without removing edges.
Time:
O(E).
"""
capacity = self._capacity
for edge in self._position:
capacity[edge] += capacity[edge ^ 1]
capacity[edge ^ 1] = 0
def min_cut(self, source: int) -> list[bool]:
"""Return vertices reachable through positive residual edges.
After maximum flow, this is the source side of a minimum cut.
Time:
O(V + E).
"""
N = self._N
graph = self._graph
to = self._to
capacity = self._capacity
visited = [False] * N
visited[source] = True
stack = [0] * N
stack[0] = source
size = 1
while size:
size -= 1
v = stack[size]
for edge in graph[v]:
u = to[edge]
if capacity[edge] and not visited[u]:
visited[u] = True
stack[size] = u
size += 1
return visited
def size(self) -> int:
"""Return the number of vertices.
Time:
O(1).
"""
return self._N
def edge_count(self) -> int:
"""Return the number of original edges.
Time:
O(1).
"""
return len(self._position)
def __str__(self) -> str:
"""Return the graph size and edge count.
Time:
O(1).
"""
return (
f"MaxFlow(N={self._N}, "
f"edges={len(self._position)})"
)
def solve():
N, M, S, T = LI()
S -= 1
T -= 1
flow = MaxFlow(N)
for i in range(M):
u, v, c = LI(1)
c += 1
flow.add_edge(u, v, c)
print(flow.max_flow(S, T))
return
if __name__ == "__main__":
T = 1
# T = II()
for _ in range(T):
solve()
sys.stdout.write("\n".join(_buf) + "\n")