TestCase/AOJ/2313.test.py

• View this file on GitHub
• Last update: 2022-01-04 20:45:42+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313

Depends on

• 最大流 (Dinic 法) (Flow/MaxFlow.py)

Code

# verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313
import sys
input = sys.stdin.readline

from Flow.MaxFlow import MaxFlow


def main():
    # verify: add_edge, get_edge, change_edge, max_flow
    n, e, q = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(e)]
    queries = [list(map(int, input().split())) for i in range(q)]

    mf = MaxFlow(n)
    label = {}
    idx = 0
    for u, v in edges:
        u -= 1
        v -= 1
        if v < u:
            u, v = v, u
        label[u, v] = idx
        idx += 1
        mf.add_edge(u, v, 0)
        mf.change_edge(label[u, v], 2, 1)

    flow = mf.max_flow(0, n - 1, 10 ** 9)

    for flag, u, v in queries:
        u -= 1
        v -= 1
        if v < u:
            u, v = v, u
        if flag == 1:
            label[u, v] = idx
            idx += 1
            mf.add_edge(u, v, 0)
            mf.change_edge(label[u, v], 2, 1)
            flow += mf.max_flow(0, n - 1, 10 ** 9)
        else:
            i = label[u, v]
            if mf.get_edge(i)[3] == 2:
                val = mf.max_flow(u, v, 1)
                if val == 0:
                    mf.max_flow(n - 1, 0, 1)
                    mf.max_flow(u, v, 1)
                    flow -= 1
            elif mf.get_edge(i)[3] == 0:
                val = mf.max_flow(v, u, 1)
                if val == 0:
                    mf.max_flow(n - 1, 0, 1)
                    mf.max_flow(v, u, 1)
                    flow -= 1
            mf.change_edge(label[u, v], 0, 0)

        print(flow)


if __name__ == '__main__':
    main()

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page