P3366 【模板】最小生成树(C++_(Prim算法_链式向前星)/(Kruskal算法_并查集))
程序员文章站
2024-02-29 12:44:04
...
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。
输入格式
第一行包含两个整数 N,M,表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 ,表示有一条长度为 的无向边连接结点 。
输出格式
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入 #1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出 #1
7
说明/提示
数据规模:
对于 的数据,,。
对于 的数据,,。
对于 的数据,,。
对于 的数据:,。
样例解释:
所以最小生成树的总边权为 。
思路
关于链式向前星可以参考这篇博客图的存储模式——链式向前星,链式向前星是一种逆序存储后输入的先遍历,具体的过程看过那篇博客后应该就懂了,这个其实也有模板的,精华就是add函数,链式向前星模板如下:
void add(int u, int v, int w)//链式向前星存储(逆向存储)
{
edge[++cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
下面就是Prim算法,就像是大佬说的那样Prim算法其实和最短路中的dijkstra很像,不断地贪心地向外扩充…
图片转自最小生成树算法(有兴趣也可以康康这个博客,我就是从dalao这里学到的啦~~~)
Code1(Prim)
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f
class node
{
public:
int to, next, w;
}edge[400010];
int n, m, head[200010], dis[200010], cnt = 0, ans = 0, sum = 0, vis[200010], now = 1;
void add(int u, int v, int w)//链式向前星存储(逆向存储)
{
edge[++cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
int prim()
{
memset(dis, INF, sizeof(dis));
for (int i = head[1]; i; i = edge[i].next)
dis[edge[i].to] = min(dis[edge[i].to], edge[i].w);//若两点之间出现多条边,只取最短的那条(图的重边)
while (++sum < n)//一张图的边比节点少一
{
int minn = INF;
vis[now] = 1;
for(int i=1;i<=n;i++)
if (!vis[i] && minn > dis[i])
{
minn = dis[i];
now = i;
}
ans += minn;
for (int i = head[now]; i; i = edge[i].next)
if(dis[edge[i].to]> edge[i].w&&!vis[edge[i].to])//一个节点不能走两遍
dis[edge[i].to] = edge[i].w;
}
return ans;
}
int main()
{
memset(head, 0, sizeof(head));
int u, v, w;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
cout << prim();
return 0;
}
Code2(Kruskal)
Kruskal算法的思想比Prin好理解一些。先把边按照权值进行排序,用贪心的思想优先选取权值较小的边,并依次连接,若出现环则跳过此边(用并查集来判断是否存在环)继续搜,直到已经使用的边的数量比总点数少一即可。
#include<bits/stdc++.h>
using namespace std;
class node
{
public:
int u, v, w;
}edge[400010];
int n, m, f[5010], ans = 0, num = 0, t1, t2;
bool cmp(node a, node b){
return a.w < b.w;
}
int find(int k)
{
if (f[k] == k)
return k;
return f[k] = find(f[k]);
}
void kruskal()
{
sort(edge + 1, edge + 1 + m, cmp);
for (int i = 1; i <= m; i++)
{
t1 = find(edge[i].u);
t2 = find(edge[i].v);
if (t1 == t2)
continue;
ans += edge[i].w;
f[t1] = t2;
if (++num == n - 1)//最小生成树的边比节点少一
break;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
f[i] = i;//初始化并查集
for (int i = 1; i <= m; i++)
cin >> edge[i].u >> edge[i].v >> edge[i].w;
kruskal();
cout << ans;
return 0;
}
下一篇: iptables命令详解和使用案例