#yukicoder390G Game World for PvP ''' んと、2チームに分配する問題か。状態を保持したDPでよさそうだ。 と思ったが2**60はいくらなんでもbitDPできない。 フロー・・・か?最小カット・・・なのか? でもそれだと連携の部分が表現できないな。 じゃあDPだな。 うーん、どうやってもうまくいかない。半分全列挙かな。 でも2**30 も大概だぞ。 事前にチームAに配属させて、チームBに転属させてゆく。 だめだな。燃やす埋める問題だ。きっつ。 両方チームAだと賞金、なら大丈夫らしい。 事前に賞金をもらった状態で開始。 ダミーノードを用意、燃やすとコスト0、埋めると賞金ぶんのコスト。 ダミーノードからA1A2にはコスト無限大の辺。 Reference: https://ikatakos.com/pot/programming_algorithm/graph_theory/maximum_flow/burn_bury_problem これ想定解が燃やす埋める問題だったらごめんだな。 →燃やす埋める問題でした せっかくなので解いておく ''' f=lambda:list(map(int,input().split())) N,S,T=f(); E=f(); R=f(); C=[f() for _ in range(N)] #最大流 Vを入力してください V=N+2 from collections import deque # V: 頂点数 G=[[] for i in range(V)] # # def add_edge(u,v,c): # G[u].append([v,c,len(G[v]) ]) # Gには [移動先の頂点, 容量, 逆辺の位置] を記入。 G[v].append([u,0,len(G[u])-1]) # G[u][辺番号] でここにアクセスできる。逆辺は容量0。 # def BFS(s): # D=[-1]*V; D[s]=0; Q=deque([s]) # while Q: # now=Q.popleft() # for nxt,cap,_ in G[now]: # 容量が残っている辺のみを有効な辺として扱う if cap>0 and D[nxt]<0: # D[nxt]=D[now]+1 # Q.append(nxt) # return D # # def DFS(v,fin,total,removed,D): # この頂点以遠でどれだけのフローを流したかを返す if v==fin: return total # ゴールに到達した場合、マックスで流す while removed[v]0 and D[v]0: # このDFSでゴールへの流量が発生した場合 G[v][removed[v]][1]-=flow G[nxt][rev][1]+=flow # return flow # removed[v]+=1 # このDFSでゴールしなかった場合、辺を削除して扱う return 0 # 最低でも1回のDFSごとに1個の辺が削除される # def Calc_max(s,fin): # flow=0 # while True: # 操作1: BFSで辺を引き直す D=BFS(s) # 配列Dは毎回作り直す if D[fin]<0: return flow # これ以上流せなくなった場合は解を出力 removed=[0]*V # removed配列はBFSするたびに作り直す while True: # 操作2: DFSで最短距離のフローを流す f=DFS(s,fin,1e10,removed,D) if f==0: break # 最短距離でフローが流せなくなったらbreak flow+=f # 操作1に戻り反復 お疲れ様でした for i in E: add_edge(N,i-1,10**18) for i in R: add_edge(i-1,N+1,10**18) for i in range(N): for j in range(N): add_edge(i,j,C[i][j]) if i!=j else None print(sum(sum(C[i]) for i in range(N))//2-Calc_max(N,N+1))