克鲁斯卡尔算法求最小生成树
这道题刚开始看,感觉有点抽象.
但仔细分析,会发现这道题非常简单.
首先条件一告诉我们,我们需要找出一颗生成树.
那最后输出的s一定等于n-1,跑都跑不掉.
再看条件三(条件二基本没用),
其实就是要让我们是这颗生成树中的最大边权尽量小.
那还用说,就是求最小生成树呀.
时间复杂度 $O(nlogn)$
C++ 代码
#include<bits/stdc++.h>
#define N 10010
using namespace std;
int n,m,k,tot,ans=-1;
int f[N];
struct node{
int from,to,dis;
}e[N];
bool rule(const node &a,const node &b){
return a.dis<b.dis;
}
int Find(int v){//并查集基本操作
if(f[v]==v)
return v;
return f[v]=Find(f[v]);
}
void merge(int x,int y){//并查集基本操作
f[Find(y)]=Find(x);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].dis);
for(int i=1;i<=n;i++)//并查集初始化
f[i]=i;
sort(e+1,e+1+m,rule);
for(int i=1;i<=m;i++){
if(k==n-1)
break;
int u=e[i].from,v=e[i].to;
if(Find(u)!=Find(v)){
merge(u,v);
ans=max(ans,e[i].dis);//取最大值
k++;
}
}
printf("%d %d\n",n-1,ans);
return 0;
}