题解 P1111 【修复公路】

· · 题解

【分析题目】

题目不长，也好理解。就是通过添加边，求在何时能够满足形成一个连通图。

【算法分析】

我们可以模拟加边，加一次就判断是否为连通图。如果到最后还没有形成连通图，输出-1。

不过如何判断是否形成了一个连通图？

并查集（Union Find Set）

顾名思义，就是一种可以进行如下两种操作的集合：

1.合并两个集合

2.查询A元素与B元素是否在同一集合内

用并查集可以干什么？

既然这里说到并查集，肯定和题目有关系。我们可以利用操作1来加边，利用操作2来判断是否为连通图。

【代码实现】

并查集的实现

inline void yu(int n)
{
    for(int i=1;i<=s;i++)
        f[i]=i;
}//预处理
inline int fi(int x)
{
    if(f[x]!=x)
        f[x]=fi(f[x]);
    return f[x];
}//追根溯源（路径压缩）
inline void merge(int x,int y)
{
    f[fi(x)]=f[fi(y)];
}//操作1
inline int check(int i,int j)
{
    retrun fi(i)==fi(i-1);
}//操作2

这一题只需要把操作2改一改，就可以得到90分

inline int check()
{
    for(register int i=2;i<=n;i++)
    {
        if(fi(i)!=fi(i-1))return 0;
    }
    return 1;
}//操作2（更改）

至于如何加边，我不相信你不会。

根据题意，自己思考。

刚刚说了这只能得90分，你可以算一下时间复杂度O(mn)。最大的点刚好1*10^8。你读入不需要时间啊？

【算法改进】

我们可以换个角度想，能不能在合并的时候就统计有多少个结点已经联通？

答案是肯定的。我们可以将操作2应用操作1中：如果两个结点分属两个不同的集合，那么必然增加一个联通数量。（自己思考一下该命题的正确性）

inline void merge(int x,int y)
{
    if(fi(x)!=fi(y))
    {
        sum++;
        f[fi(x)]=f[fi(y)];
    }
}//操作1（更改）

初始sum=1。

【代码实现】

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1005
#define maxm 100005
int f[maxn],n,m,sum=1;
struct road{
    int a,b,t;
}s[maxm];
bool cmp(const road & c,const road & d)
{
    return c.t<d.t;
}
inline void yu(int n)
{
    for(int i=1;i<=s;i++)
        f[i]=i;
}
inline int fi(int x)
{
    if(f[x]!=x)
        f[x]=fi(f[x]);
    return f[x];
}
inline void merge(int x,int y)
{
    if(fi(x)!=fi(y))
    {
        sum++;
        f[fi(x)]=f[fi(y)];    
    }
}
inline void in()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].t);
    }
    sort(s+1,s+m+1,cmp);
}
inline void Do()
{
    chu(n);
    for(register int i=1;i<=m;i++)
    {
        merge(s[i].a,s[i].b);
        if(sum>=n)
        {
            printf("%d\n",s[i].t);
            return ;
        }
    }
    printf("-1\n");
}
int main()
{
    in();
    Do();
    return 0;
}