原题链接
此题又名 小明与他优雅的麻麻 顺便我很想问问 麻麻是不是姓远坂
Kruskal最小生成树 当s与t联通时 所连的边即是题目所要求的边 虽然也能用二分做 不过看起来太麻烦了
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> using namespace std; struct nico { int x,y,cr; }road[20000+5]; int n,m,s,t,i,f[10000+5],ans; int comp(nico a,nico b) { return a.cr<b.cr; } int find(int p) { if(f[p]==p) return f[p]; f[p]=find(f[p]); return f[p]; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=m;i++) scanf("%d%d%d",&road[i].x,&road[i].y,&road[i].cr); sort(road+1,road+m+1,comp); for(i=1;i<=m;i++) { int f1=find(road[i].x); int f2=find(road[i].y); if(f1!=f2) { f[f1]=f2; ans=road[i].cr; } int fs=find(s); int ft=find(t); if(fs==ft) { printf("%d",ans); return 0; } } return 0; }