P1111 【修复公路】 并查集,联通块

2018-04-15 18:54:18


这个题要求的是什么时候所有村庄互相联通,因此要找出什么时候所有点可以连成一个联通块;这就是并查集的工作了。

题目要求“最早什么时候任意两个村庄能够通车”,那么根据贪心,这个“最早”就是从前往后数第一个满足条件的时刻。因此我们需要快速排序将各个操作按顺序来一遍。

解法1

#include<cstdio>
#include<algorithm>
int s[1001];
struct node
{
    int x,y,t;
    node(int x,int y,int t)
    {
        this->x=x;
        this->y=y;
        this->t=t;
    }
    node(){}
    friend bool operator <(node a,node b)
    {
        return a.t<b.t;
    }
}e[100001];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
}
int n;
bool check()
{
    for(int i=2;i<=n;i++)
        if(my_find(i)!=my_find(i-1))
            return false;
    return true;
}
int main()
{
    int m,a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        s[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        e[i]=*new node(a,b,c);
    }
    std::sort(e+1,e+1+m);
    for(int i=1;i<=m;i++)
    {
        my_union(e[i].x,e[i].y);
        if(check())
        {
            printf("%d\n",e[i].t);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

只T了一个点,emmm数据有点水。无论如何,暴力是过不了的。时间复杂度$O(N^2)$


那么是不是每个时刻都需要检查呢?如果每个点每个时刻都检查,这样的时间复杂度加上常数应该是够呛的。因此我们可以选择二分答案来降低时间复杂度。

解法2

#include<cstdio>
#include<algorithm>
int s[1001];
struct node
{
    int x,y,t;
    node(int x,int y,int t)
    {
        this->x=x;
        this->y=y;
        this->t=t;
    }
    node(){}
    friend bool operator <(node a,node b)
    {
        return a.t<b.t;
    }
}e[100001];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
}
int n,m;
bool check(int t)
{
    for(int i=1;i<=n;i++)
        s[i]=i;
    int i=1;
    while(e[i].t<=t&&i<=m)
    {
        my_union(e[i].x,e[i].y);
        i++;
    }
    for(int i=2;i<=n;i++)
        if(my_find(i)!=my_find(i-1))
            return false;
    return true;
}
int main()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        e[i]=*new node(a,b,c);
    }
    std::sort(e+1,e+1+m);
    int l=1,r=100001,mid=(l+r)/2;
    while(l<r)
    {
        mid=(l+r)/2;
        if(!check(mid))
            l=mid+1;
        else
            r=mid;
    }
    if(l>100000)
        printf("-1\n");
    else
        printf("%d\n",l);
    return 0;
}

用二分答案优化可以AC本题,时间复杂度为$O(Nlog_2n)$


还有没有更方便更简单的解法呢?

就是开头提到的联通块问题。并查集每并两个的点,可以判断是否属于同一个集合,如果属于同一个集合,则没有影响,如果不属于同一个集合,联通块数目$-1$,一开始有$n$个点,那么就是$n$个联通块了,这样,这道题的$O(N)$做法就出来了。

#include<cstdio>
#include<algorithm>
int s[1001];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
}
struct node
{
    int s,e,t;
    node(int s,int e,int t)
    {
        this->s=s;
        this->e=e;
        this->t=t;
    }
    node(){}
    friend bool operator <(node a,node b)
    {
        return a.t<b.t;
    }
}r[100002];
int main()
{
    int n,m,a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        s[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        r[i]=*(new node(a,b,c));
    }
    std::sort(r+1,r+1+m);
    int cnt=n,i;
    for(i=1;i<=m;i++)
    {
        if(my_find(r[i].s)!=my_find(r[i].e))
        {
            my_union(r[i].s,r[i].e);
            cnt--;
            if(cnt==1)
            {
                printf("%d\n",r[i].t);
                return 0;
            }
        }
    }
    printf("-1\n");
    return 0;
}