洛谷P3366
kruskal算法基于并查集思想qwq
prim我不会吖QAQ
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define maxn 5050 5 #define maxm 200020 6 using namespace std; 7 int n,m,num = 0,ans = 0; 8 int f[maxn]; 9 struct edge { 10 int u, v, w; 11 }e[maxm]; 12 bool cmp(edge a,edge b) { 13 if(a.w == b.w) return a.u <b.u; 14 return a.w < b.w; 15 } 16 int init(int x) {for(int i = 1; i <= x; i++) f[i] = i;} 17 int find(int x) { 18 if(x != f[x]) f[x] = find(f[x]); 19 return f[x]; 20 } 21 void merge(int x,int y) {f[y] = x;} 22 int main() { 23 scanf("%d%d",&n,&m); 24 init(n); 25 for(int i = 1; i <= m; i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 26 sort(e+1,e+m+1,cmp); 27 for(int i = 1; i <= m; i++) { 28 int r1 = find(e[i].u), r2 = find(e[i].v); 29 if(r1 != r2) { 30 merge(r1,r2); 31 ans += e[i].w; 32 num++; 33 } 34 if(num == n-1) { 35 printf("%d",ans); 36 return 0; 37 } 38 } 39 printf("orz"); 40 return 0; 41 }