最小生成树求一下就好了……
其实相当于是二分一个答案然后把所有小于这个权值的边都连上然后判断连通性,但是这个过程其实就是kruscal的过程所以只要最小生成树就可以了
#include <cstdio> #include <algorithm> using namespace std; const int N=100010; struct edge{int a,b,v;}e[N]; int n,m,cnt,ans,f[N]; int find(int a){return f[a]==a?a:f[a]=find(f[a]);} void Union(int a,int b){f[find(a)]=find(b);} bool cmp(edge a,edge b){return a.v<b.v;} int main(){ //freopen("1083.in","r",stdin);freopen("1083.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v); sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++){ if(find(e[i].a)!=find(e[i].b)) cnt++,Union(e[i].a,e[i].b),ans=e[i].v; if(cnt==n-1) break; } printf("%d %d",cnt,ans); return 0; }