結果
| 問題 | No.1316 Maximum Minimum Spanning Tree |
| ユーザー |
👑  hitonanode
|
| 提出日時 | 2020-12-11 00:34:49 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,674 bytes |
| コンパイル時間 | 147 ms |
| コンパイル使用メモリ | 12,100 KB |
| 実行使用メモリ | 63,008 KB |
| 最終ジャッジ日時 | 2023-10-20 02:13:33 |
| 合計ジャッジ時間 | 6,621 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
ソースコード
import sys
import numpy as np
from scipy.optimize import linprog
N, M, K = map(int, input().split())
A = [-1] * M
B = [-1] * M
C = [-1] * M
D = [-1] * M
c2eid = []
for eid in range(M):
A[eid], B[eid], C[eid], D[eid] = map(int, input().split())
A[eid] -= 1
B[eid] -= 1
c2eid.append((C[eid], eid))
c2eid.sort()
class DSU():
def __init__(self, N: int):
self.par = list(range(N))
self.sz = [1] * N
def find(self, x: int):
if self.par[x] != x:
self.par[x] = self.find(self.par[x])
return self.par[x]
# return x if self.par[x] == x else (self.par[x] = find(self, self.par[x]))
def unite(self, x: int, y: int):
x, y = self.find(x), self.find(y)
if x == y:
return False
if self.sz[x] < self.sz[y]:
x, y = y, x
self.par[y] = x
self.sz[x] += self.sz[y]
return True
dsu = DSU(N)
ret = 0
mstedge = [0] * M
tree = [[] for _ in range(N)]
vpar = [-1] * N
epar = [-1] * N
depth = [0] * N
for cost, eid in c2eid:
u, v = A[eid], B[eid]
if dsu.unite(u, v):
mstedge[eid] = 1
ret += C[eid] * K
tree[u].append((v, eid))
tree[v].append((u, eid))
def dfs(now: int, prv: int, dnow: int) -> None:
depth[now] = dnow
for nxt, eid in tree[now]:
if nxt != prv:
vpar[nxt] = now
epar[nxt] = eid
dfs(nxt, now, dnow + 1)
dfs(0, -1, 0)
xbound = (0, None)
vecc = [D[eid] - K * mstedge[eid] for eid in range(M)]
matA = []
vecb = []
for eid, ismst in enumerate(mstedge):
if ismst == 0:
u, v = A[eid], B[eid]
while depth[u] > depth[v]:
z = [0] * M
z[epar[u]] = 1
z[eid] = -1
matA.append(z)
vecb.append(C[eid] - C[epar[u]])
u = vpar[u]
while depth[v] > depth[u]:
z = [0] * M
z[epar[v]] = 1
z[eid] = -1
matA.append(z)
vecb.append(C[eid] - C[epar[v]])
v = vpar[v]
while u != v:
z = [0] * M
z[epar[u]] = 1
z[eid] = -1
matA.append(z)
vecb.append(C[eid] - C[epar[u]])
u = vpar[u]
z = [0] * M
z[epar[v]] = 1
z[eid] = -1
matA.append(z)
vecb.append(C[eid] - C[epar[v]])
v = vpar[v]
if len(matA) == 0:
print(ret)
else:
res = linprog(vecc, method='simplex', A_ub=matA, b_ub = vecb, bounds = [xbound] * M, options={'maxiter': 10000, 'tol': 1e-9})
if res.success:
print(ret - round(res.fun))
else:
print(-1)