试题编号： 201812-4
试题名称： 数据中心
时间限制： 1.0s
内存限制： 512.0MB
问题描述：


样例输入

4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

样例输出

4

样例说明

下图是样例说明

分析

最小生成树，求其中权值最大的边。（痛心。。。。。。）

C++程序

    #include<iostream>
    #include<algorithm>

    using namespace std;

    const int N=500100;

    struct Edge{
        int u,v,w;
        //按边权从小到大排序 
        bool operator<(const Edge &a)const
        {
            return w<a.w;
        }
    }edge[N];

    int pre[N];

    void init(int n)
    {
        for(int i=0;i<=n;i++)
          pre[i]=i;
    }

    int find(int x)
    {
        int r=x;
        while(r!=pre[r])
          r=pre[r];
        //路径压缩 
        while(x!=r)
        {
            int i=pre[x];
            pre[x]=r;
            x=i;
        }
        return r;
    }

    bool join(int x,int y)
    {
        int fx=find(x);
        int fy=find(y);
        if(fx!=fy)
        {
            pre[fx]=fy;
            return true;
        }
        return false;
    }

    int main()
    {
        int n,m,root;
        scanf("%d%d%d",&n,&m,&root);
        for(int i=0;i<m;i++)
          scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        sort(edge,edge+m);
        int ans=0,num=0;//num记录添加的边数 
        init(n);
        for(int i=0;i<m;i++)
        {
            //不构成环 
            if(join(edge[i].u,edge[i].v))
            {
                ans=edge[i].w;
                if(++num==n-1)//添加n-1条边后就能形成树，退出 
                  break;
            }
        }
        printf("%d\n",ans);
        return 0;
    }