题目:
1212 无向图最小生成树
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 收藏 关注
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
输出最小生成树的所有边的权值之和。
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
Output示例
37
分析:
最小生成树 有两种主要算法, Kruskal 和 Prim、
Kruskal 算法:
先把所有边按照权值排序, 依次选择, 把边连接的顶点加入集合,并且加上该边的权值。如果顶点已经在集合中, 择不做操作。
在Kruskal算法中, 集合的实现就用 并查集(不相交集 union-find )来实现。
Prim 算法 :
Kruskal算法是按照边来进行的, Prim 就是按照顶点来进行的。
从任意一个点出发, 把点计入树 T 中, 然后不断贪心选取 T 与其他顶点之间权值最小的边。 并加入 T 中, 就可以得到 MST 了;
实现:
Kruskal算法实现的。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 13;
struct Edge {
int from, to, dist;
Edge(int _f, int _t, int _d):\
from(_f), to(_t), dist(_d) {}
bool operator < (const Edge a) const {
return this->dist < a.dist;
}
};
struct Kruskal {
int Pre[maxn], Rank[maxn];
int n, m;
vector<Edge> edges;
void Init() {
for(int i = 0; i <= this->n; ++i) Pre[i] = i, Rank[i] = 0;
edges.clear();
}
/// UF 的实现
int Find(int x) {
if(Pre[x] == x) return x;
else return Pre[x] = Find(Pre[x]);
}
bool Union(int x, int y) {
int ax = Find(x), ay = Find(y);
if(ax == ay) return false;
if(Rank[ax] < Rank[ay])
Pre[ax] = ay;
else {
Pre[ay] = ax;
if(Rank[ay] == Rank[ax]) Rank[ax] ++;
}
return true;
}
/// Kruskal实现。
int kruskal() {
int ans = 0;
sort(edges.begin(), edges.end());
for(int i = 0; i < edges.size(); ++i) {
int u = edges[i].from, v = edges[i].to;
if(Union(u, v)) ans += edges[i].dist;
}
return ans;
}
void Add_Edges(int u, int v, int c) {
edges.push_back(Edge(u,v,c));
edges.push_back(Edge(v,u,c));
}
};
Kruskal Ks;
int main()
{
int u, v, c;
while(cin >> Ks.n >> Ks.m) {
Ks.Init();
for(int i = 0; i < Ks.m; ++i) {
cin >> u >> v >> c;
Ks.Add_Edges(u, v, c);
}
cout << Ks.kruskal() <<endl;
}
}