結果

問題 No.1316 Maximum Minimum Spanning Tree
ユーザー hitonanodehitonanode
提出日時 2020-12-11 01:38:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,188 bytes
コンパイル時間 8,460 ms
コンパイル使用メモリ 366,516 KB
実行使用メモリ 38,684 KB
最終ジャッジ日時 2024-09-19 22:01:57
合計ジャッジ時間 12,153 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,880 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
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 # 

#include <bits/stdc++.h>
using namespace std;

#include <boost/multiprecision/cpp_dec_float.hpp>

// Simplex from <https://kopricky.github.io/code/Computation_Advanced/simplex.html>
// using Float = long double;
using Float = boost::multiprecision::cpp_dec_float_100;
#define EPS 1e-30
// max c * x s.t. A*x <= b, x >= 0
class Simplex {
private:
    using Arr = vector<Float>;
    using Mat = vector<vector<Float> >;
    int* index;
    Float** a;
    int row, column, L;
 
    void Set(const Mat& A, const Arr& b, const Arr& c){
        infinity = none = false;
        row = A.size(),column = A[0].size() + 1;
        index = new int[row + column];
        int i, j;
        for(i = 0; i < row + column; i++) index[i] = i;
        L = row;
        a = new Float*[row + 2];
        for(i = 0; i < row + 2; i++) a[i] = new Float[column + 1];
        for(i = 0; i < row; i++){
            for(j = 0; j < column - 1; j++) a[i][j] = -A[i][j];
            a[i][column-1] = 1, a[i][column] = b[i];
            if(a[L][column] > a[i][column]) L = i;
        }
        for(j = 0; j < column - 1; j++) a[row][j] = c[j];
        a[row+1][column-1] = -1;
    }
 
    void solve(){
        int E, i, j;
        int* ls = new int[column + 2];
        for(E = column - 1;;){
    	    if(L < row){
                swap(index[E], index[L + column]);
                a[L][E] = 1 / a[L][E];
                int prv = column + 1;
                for(j = 0; j < column + 1; j++){
                    if(j != E){
                        a[L][j] *= -a[L][E];
                        if(abs(a[L][j]) > EPS) ls[prv] = j, prv = j;
                    }
                }
                ls[prv] = column + 1;
                for(i = 0; i < row + 2; i++){
                    if(abs(a[i][E]) < EPS || i == L) continue;
                    for(j = ls[column + 1]; j < column + 1; j = ls[j]){
                        a[i][j] += a[i][E] * a[L][j];
                    }
                    a[i][E] *= a[L][E];
                }
    	    }
    	    E = -1;
            // Float pre = EPS;
    	    for(j = 0; j < column; j++){
                if(E < 0 || index[E] > index[j]){
                    if(a[row + 1][j] > EPS || (abs(a[row + 1][j]) < EPS && a[row][j] > EPS)) E = j;
                    // if(a[row + 1][j] > pre) E = j, pre = a[row + 1][j];
                    // else if(abs(a[row + 1][j]) < EPS && a[row][j] > pre) E = j, pre = a[row][j];
                }
            }
            if(E < 0) break;
            L = -1;
            for(i = 0; i < row; i++){
                if(a[i][E] < -EPS){
                    if(L < 0) L = i;
                    else if(a[L][column] / a[L][E] - a[i][column] / a[i][E] < -EPS) L = i;
                    else if(a[L][column] / a[L][E] - a[i][column] / a[i][E] < EPS && index[L] > index[i]) L = i;
                    // if(L < 0 || a[L][column] / a[L][E] - a[i][column] / a[i][E] < EPS) L = i;
                }
            }
            if(L < 0){
                infinity = true;
                return;
            }
        }
        if(a[row + 1][column] < -EPS){
            none = true;
            return;
        }
        x.assign(column - 1, 0);
        for(i = 0; i < row; i++){
            if(index[column + i] < column - 1) x[index[column + i]] = a[i][column];
        }
        ans = a[row][column];
    }
public:
    bool infinity, none;
    Float ans;
    Arr x;
    Simplex(const Mat& A, const Arr& b, const Arr& c){
        Set(A,b,c);
        solve();
    }
};

// UnionFind Tree (0-indexed), based on size of each disjoint set
struct UnionFind {
    std::vector<int> par, cou;
    UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }
    int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (cou[x] < cou[y]) std::swap(x, y);
        par[y] = x, cou[x] += cou[y];
        return true;
    }
    int count(int x) { return cou[find(x)]; }
    bool same(int x, int y) { return find(x) == find(y); }
};


int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(M), B(M), C(M), D(M);
    vector<pair<int, int>> c2i;
    for (int eid = 0; eid < M; eid++) {
        cin >> A[eid] >> B[eid] >> C[eid] >> D[eid];
        A[eid]--, B[eid]--, c2i.emplace_back(C[eid], eid);
    }
    sort(c2i.begin(), c2i.end());
    UnionFind uf(N);
    vector<int> mstedge(M);

    vector<vector<pair<int, int>>> tree(N);
    vector<int> vpar(N, -1), epar(N, -1), depth(N);

    long long ret = 0;

    vector<long long> xdefault(M);
    for (const auto [cost, eid] : c2i) {
        const int u = A[eid], v = B[eid];
        if (uf.unite(u, v)) {
            mstedge[eid] = 1;
            ret += (long long)C[eid] * K;
            tree[u].emplace_back(v, eid);
            tree[v].emplace_back(u, eid);
        }
    }

    auto dfs = [&](auto &&self, int now, int prv, int dnow) -> void {
        depth[now] = dnow;
        for (const auto [nxt, eid] : tree[now]) {
            if (nxt != prv) {
                vpar[nxt] = now, epar[nxt] = eid;
                self(self, nxt, now, dnow + 1);
            }
        }
    };
    dfs(dfs, 0, -1, 0);

    vector<vector<Float>> matA(1, vector<Float>(M, 0));
    vector<Float> vecb{1};
    vector<Float> vecc(M);

    auto add_constraint = [&](int emst, int eadd) {
        vector<Float> v(M);
        v[emst] = 1, v[eadd] = -1;
        matA.emplace_back(v);
        vecb.emplace_back(C[eadd] - C[emst]);
    };

    for (int eid = 0; eid < M; eid++) {
        vecc[eid] = mstedge[eid] * K - D[eid];
        if (!mstedge[eid]) {
            int u = A[eid], v = B[eid];
            while (depth[u] > depth[v]) add_constraint(epar[u], eid), u = vpar[u];
            while (depth[v] > depth[u]) add_constraint(epar[v], eid), v = vpar[v];
            while (u != v) add_constraint(epar[u], eid), u = vpar[u], add_constraint(epar[v], eid), v = vpar[v];
        }
    }
    Simplex simplex(matA, vecb, vecc);
    if (simplex.infinity) puts("-1");
    else cout << ret + llround(simplex.ans) << '\n';
}
0