結果
| 問題 | No.2320 Game World for PvP |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-05-27 20:16:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 106 ms / 2,000 ms |
| コード長 | 4,049 bytes |
| コンパイル時間 | 180 ms |
| コンパイル使用メモリ | 82,196 KB |
| 実行使用メモリ | 78,240 KB |
| 最終ジャッジ日時 | 2024-06-07 19:17:20 |
| 合計ジャッジ時間 | 3,782 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 45 ms
54,572 KB |
| testcase_01 | AC | 42 ms
54,356 KB |
| testcase_02 | AC | 42 ms
54,428 KB |
| testcase_03 | AC | 44 ms
54,600 KB |
| testcase_04 | AC | 67 ms
70,512 KB |
| testcase_05 | AC | 62 ms
68,228 KB |
| testcase_06 | AC | 65 ms
68,736 KB |
| testcase_07 | AC | 73 ms
73,216 KB |
| testcase_08 | AC | 66 ms
69,952 KB |
| testcase_09 | AC | 87 ms
77,188 KB |
| testcase_10 | AC | 65 ms
71,388 KB |
| testcase_11 | AC | 96 ms
77,220 KB |
| testcase_12 | AC | 91 ms
77,548 KB |
| testcase_13 | AC | 59 ms
68,472 KB |
| testcase_14 | AC | 96 ms
77,564 KB |
| testcase_15 | AC | 71 ms
72,352 KB |
| testcase_16 | AC | 76 ms
75,048 KB |
| testcase_17 | AC | 64 ms
70,512 KB |
| testcase_18 | AC | 106 ms
78,240 KB |
| testcase_19 | AC | 95 ms
77,596 KB |
| testcase_20 | AC | 87 ms
77,400 KB |
| testcase_21 | AC | 65 ms
70,488 KB |
| testcase_22 | AC | 94 ms
77,776 KB |
| testcase_23 | AC | 91 ms
77,228 KB |
| testcase_24 | AC | 58 ms
67,776 KB |
| testcase_25 | AC | 72 ms
73,836 KB |
| testcase_26 | AC | 85 ms
77,268 KB |
| testcase_27 | AC | 41 ms
55,068 KB |
| testcase_28 | AC | 95 ms
77,716 KB |
| testcase_29 | AC | 88 ms
77,368 KB |
| testcase_30 | AC | 87 ms
77,160 KB |
| testcase_31 | AC | 97 ms
77,344 KB |
| testcase_32 | AC | 44 ms
53,988 KB |
| testcase_33 | AC | 89 ms
77,244 KB |
ソースコード
#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))