Submission

Compilation Error

Score: 0

User: yume_snowy

Problemset: รัฐบาล

Language: cpp

Time: 0.000 second

Submitted On: 2025-04-19 21:04:44

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>root;

struct edge {
    int a,b;
    ll w;
};

int findroot (int a) {
    if (root[a] == a) return a;
    return root[a] = findroot(root[a]);
}

bool comp (const edge &A,const edge &B) {
    return (A.w < B.w);
}

int main() {
    int n,m;
    cin >> n >> m;
    root.resize(n+1);
    iota(root.begin(),root.end(),0);

    vector<edge>E;

    while (m--) {
        int a,b;
        ll w;
        cin >> a >> b >> w;
        E.push_back({a,b,w});
    }

    sort(E.begin(),E.end(),comp);

    ll ans = 0;
    
    vector<edge>mst;
    
    for (auto &e : E) {
        int a = findroot(e.a);
        int b = findroot(e.b);

        if (a==b) continue;
        root[b] = a;
        ans+=e.w;
        mst.push_back(e);
    }

    cout << ans << " ";

    bool is_first = 1;
    
    for (int i=0; i<n-1; i++) {
        ll new_ans = 0;

        for (int j=0; j<=n; j++) root[j] = j;
        
        int cnt = 0;

        for (auto &e : E) {
            int a = findroot(e.a);
            int b = findroot(e.b);
            if (cnt == n-1) break;
            if (a==b || (e.a == mst[i].a && e.b == mst[i].b && e.w == mst[i].w)) continue;
            root[b] = a;
            new_ans += e.w;
            ++cnt;
        }

        if (cnt == n-1) {
            if (isfirst) {
                isfirst = 0;
                ans = new_ans;
            }
            else ans = min(ans,new_ans);
        }
    }

    cout << ans;
}