結果
問題 | No.2604 Initial Motion |
ユーザー | ニックネーム |
提出日時 | 2024-01-13 00:31:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,431 ms / 3,000 ms |
コード長 | 3,534 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 87,564 KB |
最終ジャッジ日時 | 2024-01-13 00:32:20 |
合計ジャッジ時間 | 43,724 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
55,600 KB |
testcase_01 | AC | 39 ms
55,600 KB |
testcase_02 | AC | 40 ms
55,600 KB |
testcase_03 | AC | 193 ms
77,584 KB |
testcase_04 | AC | 204 ms
77,852 KB |
testcase_05 | AC | 180 ms
77,704 KB |
testcase_06 | AC | 203 ms
77,724 KB |
testcase_07 | AC | 201 ms
77,724 KB |
testcase_08 | AC | 187 ms
77,584 KB |
testcase_09 | AC | 207 ms
77,704 KB |
testcase_10 | AC | 176 ms
77,712 KB |
testcase_11 | AC | 184 ms
77,832 KB |
testcase_12 | AC | 175 ms
77,572 KB |
testcase_13 | AC | 1,591 ms
84,056 KB |
testcase_14 | AC | 987 ms
81,876 KB |
testcase_15 | AC | 737 ms
81,252 KB |
testcase_16 | AC | 1,232 ms
82,880 KB |
testcase_17 | AC | 1,956 ms
85,092 KB |
testcase_18 | AC | 1,867 ms
85,080 KB |
testcase_19 | AC | 1,754 ms
84,880 KB |
testcase_20 | AC | 1,477 ms
83,352 KB |
testcase_21 | AC | 1,096 ms
82,292 KB |
testcase_22 | AC | 1,732 ms
84,784 KB |
testcase_23 | AC | 1,104 ms
81,864 KB |
testcase_24 | AC | 1,593 ms
83,828 KB |
testcase_25 | AC | 2,330 ms
84,984 KB |
testcase_26 | AC | 1,347 ms
82,664 KB |
testcase_27 | AC | 1,001 ms
81,900 KB |
testcase_28 | AC | 1,285 ms
82,920 KB |
testcase_29 | AC | 1,668 ms
83,412 KB |
testcase_30 | AC | 1,035 ms
81,236 KB |
testcase_31 | AC | 1,332 ms
83,468 KB |
testcase_32 | AC | 1,463 ms
83,128 KB |
testcase_33 | AC | 107 ms
79,000 KB |
testcase_34 | AC | 1,584 ms
83,224 KB |
testcase_35 | AC | 2,190 ms
87,564 KB |
testcase_36 | AC | 2,431 ms
85,640 KB |
testcase_37 | AC | 124 ms
79,408 KB |
testcase_38 | AC | 108 ms
76,604 KB |
testcase_39 | AC | 113 ms
77,136 KB |
testcase_40 | AC | 2,050 ms
83,276 KB |
testcase_41 | AC | 2,064 ms
83,532 KB |
ソースコード
import heapq class mcf_graph(): n=1 pos=[] g=[[]] def __init__(self,N): self.n=N self.pos=[] self.g=[[] for i in range(N)] def add_edge(self,From,To,cap,cost): assert 0<=From and From<self.n assert 0<=To and To<self.n m=len(self.pos) self.pos.append((From,len(self.g[From]))) self.g[From].append([To,len(self.g[To]),cap,cost]) self.g[To].append([From,len(self.g[From])-1,0,-cost]) def flow(self,s,t,flow_limit=-1-(-1<<63)): return self.slope(s,t,flow_limit)[-1] def slope(self,s,t,flow_limit=-1-(-1<<63)): assert 0<=s and s<self.n assert 0<=t and t<self.n assert s!=t ''' variants (C = maxcost): -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0 reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge ''' dual=[0 for i in range(self.n)] dist=[0 for i in range(self.n)] pv=[0 for i in range(self.n)] pe=[0 for i in range(self.n)] vis=[False for i in range(self.n)] def dual_ref(): for i in range(self.n): dist[i]=-1-(-1<<63) pv[i]=-1 pe[i]=-1 vis[i]=False que=[] heapq.heappush(que,(0,s)) dist[s]=0 while(que): v=heapq.heappop(que)[1] if vis[v]:continue vis[v]=True if v==t:break ''' dist[v] = shortest(s, v) + dual[s] - dual[v] dist[v] >= 0 (all reduced cost are positive) dist[v] <= (n-1)C ''' for i in range(len(self.g[v])): e=self.g[v][i] if vis[e[0]] or (not(e[2])):continue ''' |-dual[e.to]+dual[v]| <= (n-1)C cost <= C - -(n-1)C + 0 = nC ''' cost=e[3]-dual[e[0]]+dual[v] if dist[e[0]]-dist[v]>cost: dist[e[0]]=dist[v]+cost pv[e[0]]=v pe[e[0]]=i heapq.heappush(que,(dist[e[0]],e[0])) if not(vis[t]): return False for v in range(self.n): if not(vis[v]):continue dual[v]-=dist[t]-dist[v] return True flow=0 cost=0 prev_cost=-1 result=[(flow,cost)] while(flow<flow_limit): if not(dual_ref()): break c=flow_limit-flow v=t while(v!=s): c=min(c,self.g[pv[v]][pe[v]][2]) v=pv[v] v=t while(v!=s): self.g[pv[v]][pe[v]][2]-=c self.g[v][self.g[pv[v]][pe[v]][1]][2]+=c v=pv[v] d=-dual[s] flow+=c cost+=c*d if(prev_cost==d): result.pop() result.append((flow,cost)) prev_cost=cost return result from collections import Counter k,n,m = map(int,input().split()) a = Counter(map(int,input().split())) b = list(map(int,input().split())) g = mcf_graph(n+2) for i,v in a.items(): g.add_edge(0,i,v,0) for i,v in enumerate(b,1): g.add_edge(i,n+1,v,0) for _ in range(m): u,v,d = map(int,input().split()) g.add_edge(u,v,k,d); g.add_edge(v,u,k,d) print(g.flow(0,n+1)[1])