#1182505 (PyPy3) No.3668 Minimum Cut

• 問題: No.3668 Minimum Cut
• ユーザー: lif4635
• 提出日時: 2026-09-04 22:50:13
• 言語: PyPy3 (7.3.23)
• 結果: TLE
• 実行時間: -
• コード長: 11,685 bytes
• コンパイル時間: 760 ms
• コンパイル使用メモリ: 96,456 KB
• 実行使用メモリ: 93,736 KB
• 最終ジャッジ日時: 2026-09-04 23:01:22
• 合計ジャッジ時間: 7,535 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 21 TLE * 1 -- * 17

ソースコード

# 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 MaxFlowGraph:
    __slots__ = ("n", "graph", "pos")

    def __init__(self, n):
        assert n >= 0
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

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

    def add_edge(self, source, target, capacity):
        assert 0 <= source < self.n and 0 <= target < self.n and capacity >= 0
        graph = self.graph
        source_id = len(graph[source])
        target_id = len(graph[target])
        if source == target:
            target_id += 1
        self.pos.append((source, source_id))
        graph[source].append([target, target_id, capacity])
        graph[target].append([source, source_id, 0])
        return len(self.pos) - 1

    def get_edge(self, i):
        source, index = self.pos[i]
        edge = self.graph[source][index]
        reverse = self.graph[edge[0]][edge[1]]
        return source, edge[0], edge[2] + reverse[2], reverse[2]

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

    def residual_graph(self, include_zero=False):
        """Return ``(to, residual_capacity)`` rows of the residual graph."""
        if include_zero:
            return [[(edge[0], edge[2]) for edge in row] for row in self.graph]
        return [
            [(edge[0], edge[2]) for edge in row if edge[2]]
            for row in self.graph
        ]

    def change_edge(self, i, capacity, flow):
        assert 0 <= flow <= capacity
        source, index = self.pos[i]
        edge = self.graph[source][index]
        reverse = self.graph[edge[0]][edge[1]]
        edge[2] = capacity - flow
        reverse[2] = flow

    def _send_one(self, source, sink, limit, level, current):
        graph = self.graph
        stack_v = [source]
        stack_e = []
        stack_cap = [limit]
        n = self.n
        while stack_v:
            v = stack_v[-1]
            if v == sink:
                flow = stack_cap[-1]
                for u, i in stack_e:
                    edge = graph[u][i]
                    edge[2] -= flow
                    graph[edge[0]][edge[1]][2] += flow
                return flow

            edges = graph[v]
            i = current[v]
            next_level = level[v] + 1
            while i < len(edges):
                edge = edges[i]
                if edge[2] and level[edge[0]] == next_level:
                    break
                i += 1
            current[v] = i
            if i == len(edges):
                level[v] = n
                stack_v.pop()
                stack_cap.pop()
                if stack_e:
                    parent, edge_id = stack_e.pop()
                    current[parent] = edge_id + 1
                continue

            edge = edges[i]
            stack_e.append((v, i))
            stack_v.append(edge[0])
            stack_cap.append(min(stack_cap[-1], edge[2]))
        return 0

    def flow(self, source, sink, flow_limit=None):
        assert 0 <= source < self.n and 0 <= sink < self.n and source != sink
        graph = self.graph
        if flow_limit is None:
            flow_limit = sum(edge[2] for edge in graph[source])
        assert flow_limit >= 0
        total = 0
        n = self.n
        while total < flow_limit:
            level = [-1] * n
            level[source] = 0
            que = [source]
            for v in que:
                next_level = level[v] + 1
                for edge in graph[v]:
                    if edge[2] and level[edge[0]] < 0:
                        level[edge[0]] = next_level
                        que.append(edge[0])
            if level[sink] < 0:
                break
            current = [0] * n
            while total < flow_limit:
                pushed = self._send_one(
                    source, sink, flow_limit - total, level, current
                )
                if pushed == 0:
                    break
                total += pushed
        return total

    max_flow = flow
    run = flow

    def min_cut(self, source):
        assert 0 <= source < self.n
        visited = [False] * self.n
        visited[source] = True
        que = [source]
        graph = self.graph
        for v in que:
            for edge in graph[v]:
                if edge[2] and not visited[edge[0]]:
                    visited[edge[0]] = True
                    que.append(edge[0])
        return visited

    def min_cut_edges(self, source):
        """Return original edges crossing the current source-side minimum cut.

        Each entry is ``(edge_id, source, target, capacity, flow)``.
        """
        reachable = self.min_cut(source)
        result = []
        for edge_id in range(len(self.pos)):
            first, second, capacity, flow = self.get_edge(edge_id)
            if reachable[first] and not reachable[second]:
                result.append((edge_id, first, second, capacity, flow))
        return result

    def flow_value(self, source):
        """現在のflowのsourceから外へ出る正味流量を返す。"""
        if not 0 <= source < self.n:
            raise IndexError("source is outside the graph")
        value = 0
        for edge_id in range(len(self.pos)):
            first, second, _, flow = self.get_edge(edge_id)
            if first == source:
                value += flow
            if second == source:
                value -= flow
        return value

    def flow_paths(self, source, sink):
        """現在の正のflowをsource-sink pathへ分解する。"""
        if not 0 <= source < self.n or not 0 <= sink < self.n:
            raise IndexError("source or sink is outside the graph")
        if source == sink:
            raise ValueError("source and sink must be distinct")
        edge_data = self.edges()
        remaining = [edge[3] for edge in edge_data]
        outgoing = [[] for _ in range(self.n)]
        for edge_id, edge in enumerate(edge_data):
            if remaining[edge_id]:
                outgoing[edge[0]].append(edge_id)
        result = []
        while True:
            parent_edge = [-1] * self.n
            parent_edge[source] = -2
            queue = [source]
            for vertex in queue:
                if vertex == sink:
                    break
                for edge_id in outgoing[vertex]:
                    if remaining[edge_id] == 0:
                        continue
                    target = edge_data[edge_id][1]
                    if parent_edge[target] == -1:
                        parent_edge[target] = edge_id
                        queue.append(target)
            if parent_edge[sink] == -1:
                break
            edge_ids = []
            vertex = sink
            amount = None
            while vertex != source:
                edge_id = parent_edge[vertex]
                edge_ids.append(edge_id)
                flow = remaining[edge_id]
                if amount is None or flow < amount:
                    amount = flow
                vertex = edge_data[edge_id][0]
            edge_ids.reverse()
            vertices = [source]
            for edge_id in edge_ids:
                remaining[edge_id] -= amount
                vertices.append(edge_data[edge_id][1])
            result.append((amount, vertices, edge_ids))
        return result


MaxFlow = MaxFlowGraph


def feasible_circulation(n, edges):
    """各辺のlower以上upper以下を満たすcirculationを1つ返す。"""
    edges = list(edges)
    source = n
    sink = n + 1
    graph = MaxFlowGraph(n + 2)
    balance = [0] * n
    original = []
    for first, second, lower, upper in edges:
        if not 0 <= first < n or not 0 <= second < n:
            raise IndexError("edge endpoint is out of range")
        if not 0 <= lower <= upper:
            raise ValueError("edge bounds must satisfy 0 <= lower <= upper")
        original.append((graph.add_edge(first, second, upper - lower), lower))
        balance[first] -= lower
        balance[second] += lower
    demand = 0
    for vertex, value in enumerate(balance):
        if value > 0:
            graph.add_edge(source, vertex, value)
            demand += value
        elif value < 0:
            graph.add_edge(vertex, sink, -value)
    if graph.flow(source, sink) != demand:
        return None
    return [lower + graph.get_edge(edge_id)[3]
            for edge_id, lower in original]


def max_flow_with_bounds(n, edges, source, sink):
    """各辺のlower/upperを満たすsource-sink flowの最大値と辺flowを返す。"""
    if source == sink or not 0 <= source < n or not 0 <= sink < n:
        raise ValueError("source and sink must be distinct valid vertices")
    edges = list(edges)
    super_source = n
    super_sink = n + 1
    graph = MaxFlowGraph(n + 2)
    balance = [0] * n
    original = []
    upper_sum = 0
    for first, second, lower, upper in edges:
        if not 0 <= first < n or not 0 <= second < n:
            raise IndexError("edge endpoint is out of range")
        if not 0 <= lower <= upper:
            raise ValueError("edge bounds must satisfy 0 <= lower <= upper")
        original.append((graph.add_edge(first, second, upper - lower), lower))
        balance[first] -= lower
        balance[second] += lower
        upper_sum += upper
    bridge = graph.add_edge(sink, source, upper_sum + 1)
    auxiliary = []
    demand = 0
    for vertex, value in enumerate(balance):
        if value > 0:
            auxiliary.append(graph.add_edge(super_source, vertex, value))
            demand += value
        elif value < 0:
            auxiliary.append(graph.add_edge(vertex, super_sink, -value))
    if graph.flow(super_source, super_sink) != demand:
        return None
    base_flow = graph.get_edge(bridge)[3]
    graph.change_edge(bridge, 0, 0)
    for edge_id in auxiliary:
        graph.change_edge(edge_id, 0, 0)
    value = base_flow + graph.flow(source, sink)
    flows = [lower + graph.get_edge(edge_id)[3]
             for edge_id, lower in original]
    return value, flows


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


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

print(g.max_flow(s, t))