最小生成树
最小生成树就是把连通图的M条边变成N-1条边并且要求权值最小。(经典求最值)
而刚刚好有两个算法可以拿来解决这个问题分别是prim和kruskal。
如果把prim比作bellman-Ford那kruskal就是dijkstra了。
刚好也对应上了稀疏图和稠密图两个算法。
Kruskal
这个算法的思路简单粗暴(毕竟是贪心)。
把所有的边拿出来排序。然后挑出最小的N-1条边就可以了。
这想法是很好的但是实现起来的话很快就会发现没办法保证这样出来的是需要的树阿!
因为这样做出来的不一定是树,有些点会重复拿出边也是有概率的。
所以就需要给它们打上标记当前正在生成的树有没有包含了这些点。
但这个标记是一块一块的它并不是一条链可以很顺畅的串在一起,如果很多串串在一起的话效率未免太低。
所以就需要到并查集。
接下来思路就清晰了如果拿出来的边两点都在集合里就跳过不是的话则加入且合并。
关于无解的情况用一个计数器就可以解决,如果这个计数器结尾没有达到n-1的话则失败。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int sz=2e5+1;
int n,m,f[sz];
struct nd{
int x,y,z;
bool operator< (const nd &a)const{return z<a.z;}
}g[sz];
int fd(int x){return x==f[x]?x:f[x]=fd(f[x]);}
int main()
{
int i,x,y,s=0,ct=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)f[i]=i;
for(i=1;i<=m;++i)scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].z);
sort(g+1,g+1+m);
for(i=1;i<=m;++i)
{
x=fd(g[i].x);y=fd(g[i].y);
if(x!=y)f[x]=y,s+=g[i].z,++ct;
}
if(ct<n-1)printf("impossible");
else printf("%d",s);
return 0;
}