Luogu

算法

最简单的方法就是直接模拟然后判联通,但时间无法忍受。

其实这道题是一道最小生成树的题。把修复时间看成边权,就变成了求最小生成树的最长边,模板改一下即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
struct Edge
{
    int x,y,d;
}e[200010]; //边
int g[5010][5010]; //邻接矩阵
int root[5010]; //并查集
int n,m;
int tl=0,te=0,ans=-1;
inline bool cmp(const Edge a,const Edge b)
{
    return (a.d<b.d);
}
inline int find(int k)
{
    if (root[k]!=k) root[k]=find(root[k]);
    return root[k];
}
void Kruscal() //求最小生成树
{
    int i,j,k;
    for (k=1;k<=m;k++)
    {
        i=find(e[k].x);
        j=find(e[k].y);
        if (i!=j)
        {
            te++;
            tl+=e[k].d;
            ans=max(ans,e[k].d); //更新最长边 
            root[j]=i;
            if (te==n-1) break;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) root[i]=i; //初始化
    for (int i=1;i<=m;i++) //建图
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].d);
        g[e[i].x][e[i].y]=g[e[i].y][e[i].x]=e[i].d;
    }
    sort(e+1,e+m+1,cmp); //排序
    Kruscal();
    if (te<n-1) printf("-1\n"); //不连通
    else printf("%d\n",ans); //输出最长边
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 25 PM