QAQ 二分大法好 二分答案，如果s到t mid就找大了 不能到 mid找小了
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int head[40000],net[40000],to[40000],cost[40001]; int s,t; int d[40000],f[10001]; int cnt; void add(int x,int y,int c) { cnt++; cost[cnt]=c; to[cnt]=y; net[cnt]=head[x]; head[x]=cnt; } int dfs(int b) { memset(f,0,sizeof(f)); f[s]=1; d[1]=s; int h=0,tail=1; while(h<tail) { h++; int dd=d[h]; for(int i=head[dd];i;i=net[i]) { if(cost[i]<=b&&f[to[i]]==0) { int tmp=to[i]; if(tmp==t) return 1; f[tmp]=1; d[++tail]=tmp; } } } return 0; } int main() { int n,m; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int x,y,c; scanf("%d%d%d",&x,&y,&c); add(x,y,c); add(y,x,c); } int l=1,r=10000; while(l<r) { int mid=(l+r)/2; if(dfs(mid)) r=mid; else l=mid+1; } printf("%d",r); return 0; }方法2：将边排序，从小枚举，当s与t在一个连通块的时候，此时的cost值即为答案
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; struct hh{ int x1; int y1; int cost; }a[99999]; int fat[99999]; int ff(int x) { if(fat[x]!=x) fat[x]=ff(fat[x]); return fat[x]; } int my_comp(const hh&a,const hh&b) { if(a.cost<b.cost) return 1; return 0; } int main() { int n,m,s,t; scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=n;i++) fat[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a[i].x1,&a[i].y1,&a[i].cost); } sort(a+1,a+m+1,my_comp); int i; for(i=1;i<=m;i++) { int x=a[i].x1; int y=a[i].y1; fat[ff(x)]=ff(y); if(ff(s)==ff(t)) break; } printf("%d",a[i].cost); return 0; }