結果

問題 No.1316 Maximum Minimum Spanning Tree
コンテスト
ユーザー hitonanode
提出日時 2020-12-11 00:34:49
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,674 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 74,008 KB
最終ジャッジ日時 2024-09-19 22:01:44
合計ジャッジ時間 6,628 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1 TLE * 1
other AC * 1 WA * 2 TLE * 1 -- * 74
権限があれば一括ダウンロードができます

ソースコード

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