Submission #1416748

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1LL<<59)

int k;

class UF{
private:
    vector<int> par,rank,elm;
    vector<vector<int>> elmList;	//don't be validated
public:
    int groups;
    
    UF(int __size):par(__size) , rank(__size,0) , elm(__size,1) , groups(__size), elmList(__size){
        rep(i,__size)elmList[i] = vector<int>(1,i);
        for(int i=0;i<__size;i++)par[i]=i;
    }
    
    int getElements(int n){ return elm[find(n)]; }
    vector<int> getElementsList(int n){ return elmList[find(n)]; }
    
    int find(int x){
        if(par[x]==x) {
            return x;
        }else{
            return par[x]=find(par[x]);
        }
    }
    
    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        
        groups--;
        if(rank[x]<rank[y]){
            par[x]=y;
            elm[y]+=elm[x];
            for(auto &e:elmList[x])elmList[y].pb(e);
            
        }else{
            par[y]=x;
            elm[x]+=elm[y];
            for(auto &e:elmList[y])elmList[x].pb(e);
            if(rank[x]==rank[y])rank[x]++;
        }
    }
    
    bool isSame(int x,int y){
        return find(x)==find(y);
    }
};

#define MAX_V 100
struct edge{int to,cost;};
int kruskal(int v, vector<edge> G[MAX_V], pii edg){
    int ret=0;
    vector<pair<int,pii>> edges;
    
    rep(i,MAX_V)for(auto &e:G[i])edges.pb(make_pair(e.cost,pii(i,e.to)));
    
    sort(all(edges));
    reverse(all(edges));
    
    UF uf(v);
    rep(i,edges.size()){
        if(uf.groups==k)return ret;
        int c,u,v;
        c = edges[i].first;
        tie(u,v) = edges[i].second;
        if( min(u,v)==edg.first && max(u,v)==edg.second )continue;
        
        if(!uf.isSame(u,v)){
            uf.unite(u,v);
            ret+=c;
        }
    }
    return ret;
}



signed main(){
    int v,e;
    cin>>v>>e>>k;
    
    vector<edge> G[MAX_V];
    vector<pii> edges;
    edges.pb(pii(-1,-1));
    
    int sum = 0;
    rep(i,e){
        int s,t,c;
        cin>>s>>t>>c;
        sum+=c;
        s--,t--;
        if(s>t)swap(s,t);
        edges.pb(pii(s,t));
        G[s].pb(edge{t,c});
        G[t].pb(edge{s,c});
    }
    
    int ans = INF;
    for(auto e:edges){
        ans = min(ans,sum-kruskal(v,G,e));
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result