結果
問題 | No.1324 Approximate the Matrix |
ユーザー |
|
提出日時 | 2020-12-22 12:36:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,268 ms / 2,000 ms |
コード長 | 2,100 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 90,488 KB |
最終ジャッジ日時 | 2024-09-21 14:06:22 |
合計ジャッジ時間 | 17,778 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
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):N = self.N; G = self.GINF = MinCostFlow.INFres = 0H = [0]*Nprv_v = [0]*Nprv_e = [None]*Nd0 = [INF]*Ndist = [INF]*Nwhile f:dist[:] = 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 resN,K = map(int,input().split())A = list(map(int,input().split()))B = list(map(int,input().split()))p = [list(map(int,input().split())) for i in range(N)]G = MinCostFlow(2*N+2)for i in range(1,N+1):G.add_edge(0,i,A[i-1],0)for j in range(N+1,2*N+1):for k in range(A[i-1]):G.add_edge(i,j,1,2*k+1-2*p[i-1][j-N-1])for j in range(N+1,2*N+1):G.add_edge(j,2*N+1,B[j-N-1],0)f = G.flow(0,2*N+1,K)for i in range(N):for j in range(N):f += p[i][j]**2print(f)