|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> #include<cstring> #include<queue> #define PB(x) push_back(x) #define PS(x) push(x) #define MP(x,y) make_pair(x,y) using namespace std; typedef long long LL; const int MAXN=100; const int INF=2147483647; const int NINF=-1<<30; const int ERR=-1; struct E{int s,t,w;}; bool cmp(E a,E b){return a.w>b.w;} vector<E> Q; vector<E> ans; int f[MAXN]; int n,m,tot=0; int getb(int x){return f[x]==x?x:f[x]=getb(f[x]);} int main(){ getint(n);getint(m); for(int i=m;i>0;--i){E tm;getint(tm.s);getint(tm.t);getint(tm.w);Q.PB(tm);f[i]=i;} sort(Q.begin(),Q.end(),cmp); int a=0; while(ans.size()<n-1){ a++; int ps=Q[a].s,pt=Q[a].t; if(!(getb(ps)==getb(pt))){f[getb(ps)]=f[getb(pt)];ans.PB(Q[a]);tot+=Q[a].w;} } //Do YOLO return 0; } |
[Dr.Lib]Note:Algorithm – Kruskal by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.