結果

問題 No.2320 Game World for PvP
コンテスト
ユーザー navel_tos
提出日時 2023-05-27 20:16:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 111 ms / 2,000 ms
コード長 4,049 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,416 KB
最終ジャッジ日時 2024-12-26 03:45:26
合計ジャッジ時間 3,779 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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]<len(G[v]):      # removed[v] : 頂点vの辺のうち、削除した辺数
        nxt,cap,rev=G[v][removed[v]] # 0-indexedなので次の辺を見る
        if cap>0 and D[v]<D[nxt]:    # 最短距離で移動している限り、フローを保持し進む
            flow=DFS(nxt,fin,min(total,cap),removed,D)
            if flow>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))
0