N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。  收起  

输入

第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)

输出

输出最小生成树的所有边的权值之和。

输入样例

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

输出样例

37

===================================

这个是最小生成树的模板题，可以用Prim算法，也可以用Kruskal算法。这个题我用的是并查集优化的Kruskal算法。

C++代码：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn = 50003; struct Edge{ int a; int b; int c; }e[maxn]; bool cmp(Edge a,Edge b){ return a.c < b.c; } int n,m; int father[maxn]; void Init(int n){ for(int i = 1; i <= n; i++) father[i] = i; } int Find(int x){ while(x != father[x]){ father[x] = father[father[x]]; x = father[x]; } return x; } int Merge(int a,int b){ int ax = Find(a); int bx = Find(b); if(ax == bx) return 0; father[bx] = ax; return 1; } long long Kruskal(int n,int m){ long long ans = 0; for(int i = 1; i <= m; i++){ if(Merge(e[i].a,e[i].b)){ ans += e[i].c; n--; if(n == 1) return ans; } } return 0; } int main(){ cin>>n>>m; Init(n); for(int i = 1; i <= m; i++){ cin>>e[i].a>>e[i].b>>e[i].c; } sort(e+1,e+m+1,cmp); long long ans = Kruskal(n,m); cout<<ans<<endl; return 0; }

 

python题解见我的简书：https://www.jianshu.com/p/ca661b783628

转载于:https://www.cnblogs.com/Weixu-Liu/p/10901169.html