結果

問題 No.1316 Maximum Minimum Spanning Tree
ユーザー hitonanodehitonanode
提出日時 2020-12-11 00:34:49
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 2,674 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 74,008 KB
最終ジャッジ日時 2024-09-19 22:01:44
合計ジャッジ時間 6,628 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 1,202 ms
67,584 KB
testcase_02 AC 1,199 ms
68,240 KB
testcase_03 WA -
testcase_04 AC 1,203 ms
67,700 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0