N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。 Input 第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000) Output 输出最小生成树的所有边的权值之和。 Sample Input 9 14 1 2 4 2 3 8 3 4 7 4 5 9 5 6 10 6 7 2 7 8 1 8 9 7 2 8 11 3 9 2 7 9 6 3 6 4 4 6 14 1 8 8 Sample Output 37
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=1000+10;//最大点数 const int maxm=50000+10;//最大边数 int F[maxn];//并查集 int n,m; struct Edge{ int u,v,w; }edge[maxm];//存储边的信息，包括起点。终点。权值 int tol;//边数，加边前赋值为0 void addedge(int u,int v,int w) { edge[tol].u=u; edge[tol].v=v; edge[tol++].w=w; } //边权从小到大 bool cmp(Edge a,Edge b) { return a.w<b.w; } int find(int x) { if(F[x]==-1) return x; else return F[x]=find(F[x]); } //传入点数，返回最小生成树的权值，如果不连通返回-1 int Kruskal(int n) { memset(F,-1,sizeof(F)); sort(edge,edge+tol,cmp); int cnt=0;//计算加入的边数 int ans=0; for(int i=0;i<tol;i++) { int u=edge[i].u; int v=edge[i].v; int w=edge[i].w; int t1=find(u); int t2=find(v); if(t1!=t2) { ans+=w; F[t1]=t2; cnt++; } if(cnt==n-1) break; } if(cnt<n-1) return -1;//不连通 else return ans; } int main() { // freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { tol=0; int a,b,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } printf("%d\n",Kruskal(n)); } return 0; }