Kruskal
第一个要求告诉我们求的是一颗树,第三个要求告诉我们求最小生成树中的最大点权。
然后没了
参考代码
#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n,m,ans,sum,maxx;
int pre[N*N];
bool vis[N*N],flag;
struct Kruskal{
int x,y,z;
}kru[N*N];
int find(int i){
if(i==pre[i])
return i;
return pre[i]=find(pre[i]);
}
bool cmp(Kruskal a,Kruskal b){
return a.z<b.z;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
pre[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&kru[i].x,&kru[i].y,&kru[i].z);
}
sort(kru+1,kru+1+m,cmp);
for(int i=1;i<=m;i++){
int xx=find(kru[i].x);
int yy=find(kru[i].y);
if(xx==yy)
continue;
pre[xx]=yy;
maxx=max(maxx,kru[i].z);
ans++;
}
printf("%d %d",ans,maxx);
}