Submission

Compilation Error

Score: 0

User: Korticz

Problemset: รัฐบาล

Language: cpp

Time: 0.000 second

Submitted On: 2025-04-19 20:22:46

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ve,ed,a,b,c,best,sec=LLONG_MAX;
vector<int> head,sz;
vector<vector<int>> edge,used;
void dsu() {
    sz.assign(ve,1);
    for (int i=0;i<ve;i++) head[i]=i;
}
int findHead(int a) {
    if (head[a]==a) return a;
    return head[a]=findHead(head[a]);
}
void unionHead(int a,int b) {
    if (a==b) return;
    if (sz[a]<sz[b]) swap(a,b);
    sz[a]+=sz[b];
    head[b]=a;
}

int MST(int u,int v,int no) {
    int sum=0;
    dsu();
    for (auto&x:edge) {
        int st=x[1],en=x[2],w=x[0],headst=findHead(st),headen=findHead(en);
        if (st==u&&en==v&&w==no) continue;
        if (headst!=headen) {
            unionHead(headst,headen);
            sum+=w;
        }
    }
    if (cnt!=ve-1) return INT_MAX;
    return sum;
}


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>ve>>ed;
    head.resize(ve);
    for (int i=0;i<ed;i++) {
        cin>>a>>b>>c;
        a--,b--;
        edge.push_back({c,a,b});
    }
    sort(edge.begin(),edge.end());
    int sum=0,cnt=0;
    dsu();
    for (auto&x:edge) {
        int st=x[1],en=x[2],w=x[0],headst=findHead(st),headen=findHead(en);
        if (headst!=headen) {
            unionHead(headst,headen);
            sum+=w;
            used.push_back(x);
        }
    }
    best=sum;
    for (auto&x:used) {
        int tmp=MST(x[1],x[2],x[0]);
        sec=min(sec,tmp);
    }
    cout<<best<<" "<<sec;
    return 0;
}