結果
問題 | No.1678 Coin Trade (Multiple) |
ユーザー |
|
提出日時 | 2021-09-10 22:41:28 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,892 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 281,944 KB |
最終ジャッジ日時 | 2024-06-12 02:01:58 |
合計ジャッジ時間 | 28,154 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 TLE * 2 |
ソースコード
from heapq import heappush, heappopclass MinCostFlow:INF = 10**18def __init__(self, N):self.N = Nself.G = [[] for i in range(N)]def add_edge(self, fr, to, cap, cost):forward = [to, cap, cost, None]backward = forward[3] = [fr, 0, -cost, forward]self.G[fr].append(forward)self.G[to].append(backward)def flow(self, s, t, f,first=False):N = self.N; G = self.GINF = MinCostFlow.INFres = 0H = [0]*Nprv_v = [0]*Nprv_e = [None]*Nd0 = [INF]*Ndist = [INF]*Nwhile f:if first:first = Falsedist[s] = 0for v in range(N):for e in self.G[v]:nv,cap,cost,_ = eif cap > 0 and dist[v] + cost < dist[nv]:dist[nv] = dist[v] + costprv_e[nv] = eprv_v[nv] = vfor i in range(N):H[i] += dist[i]d = f; v = twhile v != s:d = min(d, prv_e[v][1])v = prv_v[v]f -= dres += d * H[t]v = twhile v != s:e = prv_e[v]e[1] -= de[3][1] += dv = prv_v[v]continuedist[:] = d0dist[s] = 0que = [(0, s)]while que:c, v = heappop(que)if dist[v] < c:continuer0 = dist[v] + H[v]for e in G[v]:w, cap, cost, _ = eif cap > 0 and r0 + cost - H[w] < dist[w]:dist[w] = r = r0 + cost - H[w]prv_v[w] = v; prv_e[w] = eheappush(que, (r, w))if dist[t] == INF:return Nonefor i in range(N):H[i] += dist[i]d = f; v = twhile v != s:d = min(d, prv_e[v][1])v = prv_v[v]f -= dres += d * H[t]v = twhile v != s:e = prv_e[v]e[1] -= de[3][1] += dv = prv_v[v]return resimport sys,randominput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N,K = mi()G = MinCostFlow(N)A = [0 for i in range(N)]for i in range(N):A[i],M = mi()B = li()for pi in B:G.add_edge(pi-1,i,1,A[pi-1]-A[i])for i in range(N-1):G.add_edge(i,i+1,K,0)f = G.flow(0,N-1,K,first=True)print(-f)