結果

問題 No.1316 Maximum Minimum Spanning Tree
コンテスト
ユーザー hitonanode
提出日時 2020-12-12 05:06:04
言語 Python3
(3.14.3 + numpy 2.4.2 + scipy 1.17.0)
結果
WA  
実行時間 -
コード長 823 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 93 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 56,672 KB
最終ジャッジ日時 2024-09-19 22:13:19
合計ジャッジ時間 87,191 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 75 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# scipy.sparse.csgraph.maximum_flow は現在32bit整数型しか扱えない 想定WA
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow

N, M, K = map(int, input().split())

A = [-1] * M
B = [-1] * M
C = [-1] * M
D = [-1] * M

c2i = []
for i in range(M):
    A[i], B[i], C[i], D[i] = map(int, input().split())
    c2i.append((C[i], i))
c2i.sort()

X = [0] * M

for ci, i in c2i:
    mf = [[0] * (N + 2) for _ in range(N + 2)]
    mf[0][A[i]] += K * N
    mf[0][B[i]] += K * N
    for a, b, x in zip(A, B, X):
        mf[0][a] += x
        mf[a][b] += x
    for j in range(N):
        mf[j + 1][N + 1] += K
    X[i] = min(D[i], round(maximum_flow(csr_matrix(mf), 0, N + 1).flow_value) - K - sum(X))

if sum(X) < K * (N - 1):
    print(-1)
else:
    print(sum([c * x for c, x in zip(C, X)]))
0