本文共 932 字，大约阅读时间需要 3 分钟。

题意是说，找出使点1到点n的连通的所有路径上权值最小边的最大值，即有路能连通所有点，这路上的最大权值为x,找出最小的x;

这是最小生成树的模板题；

可以按照最小生成树kruskal的贪心思想，依次寻找图中从小到大的边，则加入树的权值从小到大，直到1点和n点全部连通，此时加入树的边的权值即为解

代码：

代码中的有关r数组的部分可以不加。

因为没打cnt==n-1 break; wr好几次

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=500010;int fa[maxn];int r[maxn];int n,m;struct Edge{    int u;    int v;    int weight;};Edge a[maxn];void unin(){    int i;    for(i=1;i<=n;i++)    {        fa[i]=i;        r[i]=1;    }}int find(int u){    return fa[u]==u?fa[u]:fa[u]=find(fa[u]);}bool cmp(Edge x,Edge y){    return x.weight>y.weight;}void join(int u,int v){   int a=find(u);   int b=find(v);   if(a==b)    return ;   if(r[a]
       
        r[b])   {       fa[b]=a;   }   else   {       fa[a]=b;       r[b]++;   }}int main(){    int t;    scanf("%d",&t);    int p=0;    while(t--)    {        scanf("%d%d",&n,&m);        unin();        int i;        for(i=0;i
       
      
     
    
   

转载地址：http://dygji.baihongyu.com/