#1184068 (PyPy3) No.3668 Minimum Cut

• 問題: No.3668 Minimum Cut
• ユーザー: lif4635
• 提出日時: 2026-09-05 16:45:38
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 421 ms / 2,000 ms
• コード長: 10,171 bytes
• コンパイル時間: 258 ms
• コンパイル使用メモリ: 96,332 KB
• 実行使用メモリ: 94,252 KB
• 最終ジャッジ日時: 2026-09-05 16:45:50
• 合計ジャッジ時間: 9,473 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 39

ソースコード

# haru: pypy
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]

mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")

prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
# sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right
class PushRelabel:

    __slots__ = ("n", "graph", "to", "capacity", "position")

    def __init__(self, n):
        if n < 0:
            raise ValueError("number of vertices must be nonnegative")
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.to = []
        self.capacity = []
        self.position = []

    def add_vertex(self):
        self.graph.append([])
        self.n += 1
        return self.n - 1

    def add_edge(self, source, target, capacity):
        if not (0 <= source < self.n and 0 <= target < self.n):
            raise IndexError("vertex out of range")
        if not isinstance(capacity, int):
            raise TypeError("capacity must be an integer")
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        edge = len(self.to)
        self.graph[source].append(edge)
        self.to.append(target)
        self.capacity.append(capacity)
        self.graph[target].append(edge + 1)
        self.to.append(source)
        self.capacity.append(0)
        self.position.append((source, edge))
        return len(self.position) - 1

    def get_edge(self, index):
        source, edge = self.position[index]
        reverse_capacity = self.capacity[edge ^ 1]
        return (
            source,
            self.to[edge],
            self.capacity[edge] + reverse_capacity,
            reverse_capacity,
        )

    def edges(self):
        return [self.get_edge(i) for i in range(len(self.position))]

    def change_edge(self, index, capacity, flow):
        if not isinstance(capacity, int) or not isinstance(flow, int):
            raise TypeError("capacity and flow must be integers")
        if not (0 <= flow <= capacity):
            raise ValueError("flow must satisfy 0 <= flow <= capacity")
        _, edge = self.position[index]
        self.capacity[edge] = capacity - flow
        self.capacity[edge ^ 1] = flow

    def _global_relabel(self, source, sink, height, current):
        n = self.n
        unreachable = 2 * n
        height[:] = [unreachable] * n
        current[:] = [0] * n
        height[sink] = 0
        graph, to, residual = self.graph, self.to, self.capacity
        queue = [sink]
        for vertex in queue:
            next_height = height[vertex] + 1
            for edge in graph[vertex]:
                other = to[edge]
                if height[other] == unreachable and residual[edge ^ 1]:
                    height[other] = next_height
                    queue.append(other)
        height[source] = n
        queue = [source]
        for vertex in queue:
            next_height = height[vertex] + 1
            for edge in graph[vertex]:
                other = to[edge]
                if height[other] == unreachable and residual[edge ^ 1]:
                    height[other] = next_height
                    queue.append(other)

    def flow(self, source, sink, flow_limit=None):
        """Add and return flow up to ``flow_limit`` on the residual graph."""
        n = self.n
        if not (0 <= source < n and 0 <= sink < n):
            raise IndexError("vertex out of range")
        if source == sink:
            raise ValueError("source and sink must differ")
        if flow_limit is not None:
            if not isinstance(flow_limit, int):
                raise TypeError("flow limit must be an integer")
            if flow_limit < 0:
                raise ValueError("flow limit must be nonnegative")
        if flow_limit is None:
            return self._flow_unlimited(source, sink)
        if flow_limit == 0:
            return 0

        temporary_source = self.add_vertex()
        self.add_edge(temporary_source, source, flow_limit)
        try:
            return self._flow_unlimited(temporary_source, sink)
        finally:
            self.position.pop()
            self.graph[source].pop()
            self.graph.pop()
            self.to.pop()
            self.to.pop()
            self.capacity.pop()
            self.capacity.pop()
            self.n -= 1

    def _flow_unlimited(self, source, sink):
        n = self.n
        graph, to, residual = self.graph, self.to, self.capacity
        excess = [0] * n
        height = [0] * n
        current = [0] * n
        for edge in graph[source]:
            other = to[edge]
            if other == source:
                continue
            amount = residual[edge]
            if amount:
                residual[edge] = 0
                residual[edge ^ 1] += amount
                excess[other] += amount
                excess[source] -= amount

        self._global_relabel(source, sink, height, current)
        buckets = [[] for _ in range(2 * n + 1)]
        count = [0] * (2 * n + 1)
        top = -1
        for vertex, h in enumerate(height):
            count[h] += 1
            if vertex != source and vertex != sink and excess[vertex]:
                buckets[h].append(vertex)
                if h > top:
                    top = h
        work = 0
        threshold = 4 * len(to) + n

        while top >= 0:
            if not buckets[top]:
                top -= 1
                continue
            vertex = buckets[top].pop()
            if height[vertex] != top or not excess[vertex]:
                continue
            edges = graph[vertex]
            rest = excess[vertex]
            hv = height[vertex]
            index = current[vertex]
            while rest:
                if index == len(edges):
                    best = 2 * n
                    for edge in edges:
                        if residual[edge] and height[to[edge]] < best:
                            best = height[to[edge]]
                    count[hv] -= 1
                    old = hv
                    hv = best + 1
                    height[vertex] = hv
                    count[hv] += 1
                    index = 0
                    work += len(edges)
                    if old < n and not count[old]:
                        for other, h in enumerate(height):
                            if old < h < n:
                                count[h] -= 1
                                height[other] = n + 1
                                count[n + 1] += 1
                                current[other] = 0
                                if other != vertex and excess[other]:
                                    buckets[n + 1].append(other)
                                    if top < n + 1:
                                        top = n + 1
                        hv = height[vertex]
                    continue

                edge = edges[index]
                other = to[edge]
                capacity = residual[edge]
                if capacity and hv == height[other] + 1:
                    amount = rest if rest < capacity else capacity
                    residual[edge] -= amount
                    residual[edge ^ 1] += amount
                    rest -= amount
                    if not excess[other] and other != source and other != sink:
                        h = height[other]
                        buckets[h].append(other)
                        if h > top:
                            top = h
                    excess[other] += amount
                    if not rest:
                        break
                index += 1
                work += 1
            excess[vertex] = 0
            current[vertex] = index

            if work >= threshold:
                self._global_relabel(source, sink, height, current)
                buckets = [[] for _ in range(2 * n + 1)]
                count = [0] * (2 * n + 1)
                top = -1
                for other, h in enumerate(height):
                    count[h] += 1
                    if other != source and other != sink and excess[other]:
                        buckets[h].append(other)
                        if h > top:
                            top = h
                work = 0
        return excess[sink]


    def min_cut(self, source):
        if not 0 <= source < self.n:
            raise IndexError("vertex out of range")
        visited = bytearray(self.n)
        visited[source] = 1
        queue = [source]
        graph = self.graph
        to = self.to
        residual = self.capacity
        for vertex in queue:
            for edge in graph[vertex]:
                other = to[edge]
                if residual[edge] and not visited[other]:
                    visited[other] = 1
                    queue.append(other)
        return [bool(value) for value in visited]



n, m, s, t = MI()
s -= 1
t -= 1

g = PushRelabel(n)
for i in range(m):
    u, v, c = MI()
    u -= 1
    v -= 1
    g.add_edge(u, v, c)

print(g.flow(s, t))