把路按时间排序，加权size[i]表示 i 所属的并查集的个数 按顺序依次合并每条路 每次合并完判断当前并查集的size是否达到n

十五分钟搞定，复习kruscal

prim也能过的说！！！

并查集的基础练习

看错题。。

最小生成树的最大边一定是所有生成树中最小的。
因为kruskal算法保证在取到这条边之前构不成生成树

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000;
struct Node{
int from,to,cost;
}a[100001];
bool comp(const Node &a,const Node &b){
return a.cost<b.cost;
}
int n,m,root[1001];
void Kruskal();
int Findroot(int);
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
a[i].from=x;a[i].to=t;a[i].cost=z;
}
Kruskal();
return 0;
}
void Kruskal(){
int ans=0,cnt=0;
for(int i=1;i<=n;i++){
root[i]=i;
}
sort(a+1,a+m+1,comp);
for(int i=1;i<=m;i++){
int x=a[i].from,y=a[i].to;
int rx=Findroot(x),ry=Findroot(y);
if(rx==ry) continue;
else{
root[rx]=ry;cnt++;
if(a[i].cost>ans) ans=a[i].cost;
}
if(cnt==n-1) break;
}
if
}
int Findroot(int x){
if(x!=root[x]){
root[x]=Findroot(root[x]);
}
return root[x];
}

用Kruskal求最小生成树即可

回复 @=_= :
说的没错~~

Kruskal+cnt计数,如果循环到最后都没有 cnt = n -1 ;说明没有连通
输出-1,其他的就是个裸的最小生成树

居然把m打成了n

回复 @Hoskey :
写错了不知道多少次了= =看题不清楚作死的节奏

回复 @Hoskey :
写错了不知道多少次了= =看题不清楚作死的节奏

连MST都不会写了。。。
刷水太少了。。。。。。

奇葩地跪在0~n-1和1~n的问题上了……