結果
| 問題 | No.2320 Game World for PvP |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-05-27 20:16:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 156 ms / 2,000 ms |
| コード長 | 4,049 bytes |
| コンパイル時間 | 305 ms |
| コンパイル使用メモリ | 86,384 KB |
| 実行使用メモリ | 82,196 KB |
| 最終ジャッジ日時 | 2023-08-26 23:53:30 |
| 合計ジャッジ時間 | 6,201 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 95 ms
71,424 KB |
| testcase_01 | AC | 95 ms
71,344 KB |
| testcase_02 | AC | 97 ms
71,332 KB |
| testcase_03 | AC | 94 ms
70,928 KB |
| testcase_04 | AC | 121 ms
77,236 KB |
| testcase_05 | AC | 114 ms
76,992 KB |
| testcase_06 | AC | 116 ms
77,096 KB |
| testcase_07 | AC | 125 ms
77,344 KB |
| testcase_08 | AC | 117 ms
77,356 KB |
| testcase_09 | AC | 129 ms
78,068 KB |
| testcase_10 | AC | 118 ms
77,864 KB |
| testcase_11 | AC | 141 ms
78,112 KB |
| testcase_12 | AC | 136 ms
78,180 KB |
| testcase_13 | AC | 114 ms
77,448 KB |
| testcase_14 | AC | 145 ms
79,492 KB |
| testcase_15 | AC | 122 ms
77,384 KB |
| testcase_16 | AC | 127 ms
77,976 KB |
| testcase_17 | AC | 118 ms
77,860 KB |
| testcase_18 | AC | 156 ms
79,784 KB |
| testcase_19 | AC | 145 ms
79,108 KB |
| testcase_20 | AC | 134 ms
78,084 KB |
| testcase_21 | AC | 118 ms
77,468 KB |
| testcase_22 | AC | 140 ms
78,888 KB |
| testcase_23 | AC | 136 ms
78,412 KB |
| testcase_24 | AC | 112 ms
77,224 KB |
| testcase_25 | AC | 123 ms
77,520 KB |
| testcase_26 | AC | 132 ms
78,296 KB |
| testcase_27 | AC | 95 ms
70,976 KB |
| testcase_28 | AC | 152 ms
82,196 KB |
| testcase_29 | AC | 140 ms
77,864 KB |
| testcase_30 | AC | 134 ms
77,352 KB |
| testcase_31 | AC | 150 ms
78,684 KB |
| testcase_32 | AC | 96 ms
71,336 KB |
| testcase_33 | AC | 136 ms
77,528 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))