Submission #7580976

---

Source Code Expand

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from collections import deque
    class Dinic:
        def __init__(self, n):
            self.n = n
            self.links = [[] for _ in range(n)]
            self.depth = None
            self.progress = None

        def add_link(self, _from, to, cap):
            self.links[_from].append([cap, to, len(self.links[to])])
            self.links[to].append([0, _from, len(self.links[_from]) - 1])

        def bfs(self, s):
            depth = [-1] * self.n
            depth[s] = 0
            q = deque([s])
            while q:
                v = q.popleft()
                for cap, to, rev in self.links[v]:
                    if cap > 0 and depth[to] < 0:
                        depth[to] = depth[v] + 1
                        q.append(to)
            self.depth = depth

        def dfs(self, v, t, flow):
            if v == t:
                return flow
            links_v = self.links[v]
            for i in range(self.progress[v], len(links_v)):
                self.progress[v] = i
                cap, to, rev = link = links_v[i]
                if cap == 0 or self.depth[v] >= self.depth[to]:
                    continue
                d = self.dfs(to, t, min(flow, cap))
                if d == 0:
                    continue
                link[0] -= d
                self.links[to][rev][0] += d
                return d
            return 0

        def max_flow(self, s, t):
            flow = 0
            while True:
                self.bfs(s)
                if self.depth[t] < 0:
                    return flow
                self.progress = [0] * self.n
                current_flow = self.dfs(s, t, float('inf'))
                while current_flow > 0:
                    flow += current_flow
                    current_flow = self.dfs(s, t, float('inf'))
    # input
    n,g,e=map(int,input().split())
    flow=Dinic(n+1)
    for p in map(int,input().split()):
        flow.add_link(p,n,1)
        flow.add_link(n,p,1)
    for _ in range(e):
        a,b=map(int,input().split())
        flow.add_link(a,b,1)
        flow.add_link(b,a,1)
    print(flow.max_flow(0,n))
resolve()

Submission Info

Judge Result