Hust oj 1350 最小生成树问题(MST）_综合

最小生成树问题

Time Limit: 2000 MS

Memory Limit: 32767 K

Total Submit: 255(77 users)

Total Accepted: 92(61 users)

Rating:

Special Judge: No

Description

一个有 n 个结点的无向连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，
并且有保持图联通的最少的边。求解最小生成树的一个算法是Kruskal提出的kruskal算法，该算
法每次找到所有边中权值最小的一条，并判断该边的加入是否会让最小生成树出现环，如果不会则将
其作为最小生成树的一条边。

现在给出一个图的节点数N和边数M以及每条边的权值，求出该图的最小生成树的所有边权值总和。

Input

每组输入第一行为N和M，N<=10000,M<=50000,然后为M行，每行三个整数a,b,w,表示a,b之间有
一条权值为w的边。

Output

如果该图无法生成最小生成树，即原图不连通，则输出-1，否则输出最小生成树的长度。

Sample Input

3 3
1 2 1
1 3 2
2 3 4

Sample Output

真的。。。从未见过如此直白的题。。。Kruskal模板直接AC

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN=10005;
int p[MAXN],r[MAXN];int find(int v)
{if(v!=p[v]) p[v]=find(p[v]);return p[v];
}void join(int u,int v)
{int a=find(u);int b=find(v);if(a==b) return;if(r[a]<r[b])p[a]=b;else if(r[a]>r[b])p[b]=a;else{p[a]=b;r[b]++;}
}void init_set(int n)
{for(int i=1;i<=n;i++){p[i]=i;r[i]=1;}
}struct Edge
{int u;int v;int weight;
};
struct Edge edge[50005];int cmp(Edge p,Edge q)
{return p.weight<q.weight;
}int kru(int n,int m)
{init_set(n);sort(edge,edge+m,cmp);int ret=0;int cnt=0;for(int i=0;i<m;i++){int u=edge[i].u;int v=edge[i].v;if(find(u)!=find(v)){cnt++;ret+=edge[i].weight;join(u,v);}if(cnt==n-1) return ret;}return -1;
}int main()
{int n,m,a,b,w;int ans;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<m;i++){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].weight);}ans=kru(n,m);printf("%d\n",ans);}return 0;
}