結果

問題 No.3699 引き抜き交渉
コンテスト
ユーザー とりゐ
提出日時 2026-09-09 21:29:21
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 104 ms / 2,000 ms
+ 251µs
コード長 4,694 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 74 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 87,552 KB
最終ジャッジ日時 2026-09-09 21:30:02
合計ジャッジ時間 2,491 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class MaxFlow:
    _INF = 9_223_372_036_854_775_807

    def __init__(self, n=0):
        self._n = n
        self._pos = []
        self._g = [[] for _ in range(n)]  # [to, rev, cap]

    def add_edge(self, from_, to, cap):
        assert 0 <= from_ < self._n
        assert 0 <= to < self._n
        assert 0 <= cap
        m = len(self._pos)
        from_id = len(self._g[from_])
        self._pos.append([from_, from_id])
        to_id = len(self._g[to])
        if from_ == to:
            to_id += 1
        self._g[from_].append([to, to_id, cap])
        self._g[to].append([from_, from_id, 0])
        return m

    def get_edge(self, i):
        m = len(self._pos)
        assert 0 <= i < m
        _e = self._g[self._pos[i][0]][self._pos[i][1]]
        _re = self._g[_e[0]][_e[1]]
        return [self._pos[i][0], _e[0], _e[2] + _re[2], _re[2]]  # from, to, cap, flow

    def edges(self):
        m = len(self._pos)
        result = [self.get_edge(i) for i in range(m)]
        return result

    def change_edge(self, i, new_cap, new_flow):
        m = len(self._pos)
        assert 0 <= i < m
        assert 0 <= new_flow <= new_cap
        _e = self._g[self._pos[i][0]][self._pos[i][1]]
        _re = self._g[_e[0]][_e[1]]
        _e[2] = new_cap - new_flow
        _re[2] = new_flow

    def _flow_bfs(self, s, t):
        level = [-1] * self._n
        level[s] = 0
        que = [s]
        while que:
            next_que = []
            for v in que:
                for to, rev, cap in self._g[v]:
                    if cap == 0 or level[to] >= 0:
                        continue
                    level[to] = level[v] + 1
                    if to == t:
                        return level
                    next_que.append(to)
            que, next_que = next_que, que
        return level

    def flow(self, s, t, flow_limit=_INF):
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t

        flow = 0
        while flow < flow_limit:
            level = self._flow_bfs(s, t)
            if level[t] == -1:
                break

            iterator = [0] * self._n
            in_ = [0] * self._n
            out = [0] * self._n

            in_[t] = flow_limit - flow
            route = [t]
            while route:
                v = route[-1]
                if in_[v] == out[v] and v == t:
                    flow += out[t]
                    return flow
                if v == s or in_[v] == out[v]:
                    route.pop()
                    w = route[-1]
                    flow_vw = in_[v]
                    i = iterator[w]
                    to, rev, cap = self._g[w][i]
                    self._g[v][rev][2] -= flow_vw
                    self._g[w][i][2] += flow_vw
                    out[w] += flow_vw
                    continue

                for i in range(iterator[v], len(self._g[v])):
                    to, rev, cap = self._g[v][i]
                    if level[to] == -1 or level[v] <= level[to] or self._g[to][rev][2] == 0:
                        continue
                    in_[to] = min(in_[v] - out[v], self._g[to][rev][2])
                    out[to] = 0
                    route.append(to)
                    iterator[v] = i
                    break
                else:
                    iterator[v] = len(self._g[v])
                    route.pop()
                    if v == t:
                        if out[t] == 0:
                            return flow
                        flow += out[t]
                        continue
                    w = route[-1]
                    flow_vw = out[v]
                    i = iterator[w]
                    to, rev, cap = self._g[w][i]
                    self._g[v][rev][2] -= flow_vw
                    self._g[w][i][2] += flow_vw
                    out[w] += flow_vw
                    iterator[w] += 1
        return flow

    def min_cut(self, s):
        visited = [False] * self._n
        visited[s] = True
        que = [s]
        while que:
            next_que = []
            for p in que:
                for to, rev, cap in self._g[p]:
                    if cap > 0 and not visited[to]:
                        visited[to] = True
                        next_que.append(to)
            que, next_que = next_que, que
        return visited


n, m = map(int, input().split())
S = n
T = S + 1
ans = 0
G = MaxFlow(n + 2)
for i in range(n):
    a, b = map(int, input().split())
    G.add_edge(S, i, a)
    G.add_edge(i, T, b)
    ans += a + b

for _ in range(m):
    u, v, c = map(int, input().split())
    u -= 1
    v -= 1
    G.add_edge(u, v, c)
    G.add_edge(v, u, c)

print(ans - G.flow(S, T))
0