e-mon

備忘録

CodeForces Round #304 Div2 E - Soldier and Traveling

問題 : http://codeforces.com/contest/546/problem/E

内容

nの町があり,それぞれの町はm個の辺で接続されている. 現在 n_iの町に存在する a_iの兵士を同じ道を二度通らずに他の町に移動する,もしくは他の町から移動してくることで b_iにしたい. 多重辺はないが,連結であるとは限らない.可能である場合は iから jへ何人移動したかを行列にして出力すること.

解法

各頂点への流入路を初期配置,流出路を最終配置として,新たにsourceとsinkを設けることでフロー問題に帰着させ解くということであった. 具体的には,まず頂点を移動前N個,移動後N個,source,sinkの2N+2個確保し,sourceから各頂点へ各A分のcapを設け,頂点から対応のある頂点へ容量を無限大としたエッジを張り,各頂点からsinkへ各B分のcapを設ける,という方法で解ける.

雑感

人数が足りているところと,不足しているところの対応を考える問題かなぁとぐちゃぐちゃコードを書いて結局解けなかった. yukicoderでも同様にして解く問題(あちらは明白に二部グラフだったけど)があったので.典型問題なのだろうか. 良い機会なので最大流問題に今後チャレンジ出来るようにライブラリの整備を行った. 最大流問題は,今回のようにうまいこと頂点の容量を辺の容量に変換,sourceとsinkを追加して二部グラフのフローとして解くような問題とかが良くでるようなので,他のパターンも含めて色々解いておきたい.

まだPythonしかできていないので,C++版も用意すること.(加えて,Dicnic法を追加すること)

class Ford_Fulkerson:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to = to
            self.cap = cap
            self.rev = rev
        
        def __repr__(self):
            return "(to: {0} cap: {1} rev: {2})".format(self.to, self.cap, self. rev)

    def __init__(self,V):
        self.V = V
        self.size = [0 for i in range(V)]
        self.G = [[] for i in range(V)]

    def add_edge(self, _from, to, cap):
        self.size[_from]
        self.G[_from].append(self.Edge(to, cap, self.size[to]))
        self.G[to].append(self.Edge(_from, 0, self.size[_from]))
        self.size[_from] += 1
        self.size[to] += 1

    def dfs(self, v, t, f):
        if v == t: return f
        self.used[v] = True
        for i in range(len(self.G[v])):
            edge = self.G[v][i]
            if self.used[edge.to] is False and edge.cap > 0:
                d = self.dfs(edge.to, t, f if f < edge.cap else edge.cap)
                if d > 0:
                    self.G[v][i].cap -= d
                    self.G[edge.to][edge.rev].cap += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.used = [False for _ in range(self.V)]
            f = self.dfs(s, t, float('inf'))
            if f == 0:
                return flow
            flow += f

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ff = ford_fulkerson(N*2+2)
S = 1
T = N + 1

for i in range(M):
    p,q = map(int, input().split())
    ff.add_edge(p,T+q-1,10**9)
    ff.add_edge(q,T+p-1,10**9)

for i in range(N):
    ff.add_edge(i+1,T+i,10**9)
    ff.add_edge(0,S+i,A[i])
    ff.add_edge(T+i,2*N+1,B[i])

ans = [[0  for i in range(N)] for j in range(N)]
ff.max_flow(0,2*N+1)

for i in range(1,N+1):
    for v in ff.G[i]:
        if v.to != 0:
            ans[i-1][v.to-T] = ff.G[v.to][v.rev].cap

if sum(A) != sum(B):
    print('NO')
    quit()
if [sum([ans[i][j] for i in range(N)]) for j in range(N)] == B:
    print('YES')
    for a in ans:
        print(' '.join(map(str,a)))
else:
    print('NO')