洛谷 P1653 猴子 题解【并查集】【最短路】

点击量：111

    这个一年前开坑的题到现在终于解决了……

目录

题目描述

有N只猴子，第一只尾巴挂在树上，剩下的N-1只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。当然一只猴子最多抓两只另外的猴子。现在给出这N只猴子抓与被抓的信息，并且在某个时刻可能某只猴子会放掉它其中一只手的猴子，导致某些猴子落地。求每只猴子落地的时间。

输入输出格式

输入格式：

第一行两个数N、M，表示有N只猴子，并且总时间为M-1。接下来N行，描述了每只猴子的信息，每行两个数，分别表示这只猴子左手和右手抓的猴子的编号，如果是-1，表示该猴子那只手没抓其他猴子。再接下来M行，按时间顺序给出了一些猴子放手的信息，第1+N+i行表示第i-1时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子编号，后者表示其放的是哪只手，1左2右。

【数据规模】

30%的数据，N≤1000，M≤1000;

100%的数据，1≤N≤200000，1≤M≤400000。

输出格式：

共输出N行，第i行表示第i只猴子掉落的时刻，若第i只猴子岛M-1时刻以后还没掉落，就输出-1。

输入输出样例

输入样例#1：

3 2
-1 3
3 -1
1 2
1 2
3 1

输出样例#1：

-1
1
1

题解：

    在这个题中，猴子可能会成堆地掉下去，而成堆地掉下去时，我们要知道这一堆中有哪些猴子，这样我们就要用到并查集。不过并查集一般不支持拆集，所以我们应该倒着做。

    思路比较简单，只要两个集合在合并的过程中，有一个集合中含有1，那么另一个集合就是在这一时刻从树上掉下来的。而我们要维护每个集合中都有哪些元素，可以遍历一遍检验每个元素的祖先是否为这个集合的祖先，不过时间复杂度不允许。而我们知道每个猴子掉下来的时间是唯一的，我们能否做到每个猴子只在被合并时扫描到呢？

    我们可以用一个链表来维护并查集中的元素。其实没有必要在合并时把链表互相连接，而是只用连接其中一个的祖先。因为只会在当前区间合并到1时被从祖先访问，dfs一次，所以对于链表的每一个元素都进一遍它们的dfs，看曾经以他们为祖先的元素有哪些，则都在此时被合并上去了。

    为了保留1，并使处理过程更简便，我们每次合并时只把编号大的合并到编号小的上去，这样就防止了合并过程中链表互指的情况。

    还有一种做法是类似最短路的。虽然类似一棵树的结构，但实际上它是一个图，设边权为第几秒断开的，答案就是每个点到1的所有路径中边权最小的一条边的最大值。跑dijkstra最短路就行了。

Code：（并查集）

#include<cstdio>
#include<cstring>
#include<vector>
using std::vector;
vector<int> t[210000];
struct edge
{
    int x,y;
}e[410000];
int ecnt=0;
int s[210000];
int l[210000],r[210000];
int b[410000];
bool ava[410000];
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)
{
    int flag=0;
    if(my_find(x)==1||flag)
    {
        t[x].push_back(my_find(y));
        s[my_find(y)]=x;
    }
    else if(my_find(y)==1||flag)
    {
        t[y].push_back(x);
        s[my_find(x)]=y;
    }
    else
    {
        if(my_find(x)>my_find(y))//保证了大连在小上
        {
            int t=x;
            x=y;
            y=t;
        }
        t[my_find(x)].push_back(my_find(y));
        s[my_find(y)]=my_find(x);
    }

}
int ans[210000];
void add(int x,int k)//dfs过程
{
    ans[x]=k;
    for(vector<int>::iterator it=t[x].begin();it!=t[x].end();it++)
        add(*it,k);
    return;
}
int main()
{
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    memset(ava,1,sizeof(ava));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        s[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&u,&v);
        if(~u)
        {
            e[++ecnt]=edge{i,u};
            l[i]=ecnt;
        }
        if(~v)
        {
            e[++ecnt]=edge{i,v};
            r[i]=ecnt;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        if(v==1)
        {
            ava[l[u]]=0;
            b[i]=l[u];
        }
        else
        {
            ava[r[u]]=0;
            b[i]=r[u];
        }
    }
    for(int i=1;i<=ecnt;i++)
        if(ava[i]&&my_find(e[i].x)!=my_find(e[i].y))
            my_union(e[i].x,e[i].y);
    ans[1]=-1;
    for(int i=1;i<=n;i++)
        if(my_find(i)==1)
            ans[i]=-1;
    for(int i=m;i>=1;i--)
    {
        int ans1=my_find(e[b[i]].x);
        int ans2=my_find(e[b[i]].y);
        if(ans1==ans2)
            continue;
        if(ans1==1)
            add(my_find(e[b[i]].y),i-1);
        if(ans2==1)
            add(my_find(e[b[i]].x),i-1);
        my_union(e[b[i]].x,e[b[i]].y);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);

    return 0;
}

Code：（最短路）

#include<cstdio>
#include<cstring>
#include<queue>

#define min(x,y) (x<y?x:y)
using std::priority_queue;
struct edge
{
    int n,v,nxt;
    edge(int n,int v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge(){nxt=-1;}
}e[810000];
int head[210000],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,v,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,v,head[to]);
    head[to]=ecnt;
}
struct statu
{
    int n,dis;
    statu(int n,int dis)
    {
        this->n=n;
        this->dis=dis;
    }
    statu(){}
    friend bool operator <(statu a,statu b)
    {return a.dis<b.dis;}
    friend bool operator >(statu a,statu b)
    {return a.dis>b.dis;}
};

priority_queue<statu> q;

int f[210000],from[210000];
void dijk()
{
    memset(f,0x3f,sizeof(f));
    f[1]=0x3f3f3f3f;
    q.push(statu(1,0x3f3f3f3f));
    while(!q.empty())
    {
        statu k=q.top();
        q.pop();
        if(f[k.n]<k.dis)
            continue;
        for(int i=head[k.n];~i;i=e[i].nxt)
            if(min(k.dis,e[i].v)>f[e[i].n])
            {
                f[e[i].n]=min(k.dis,e[i].v);
                q.push(statu(e[i].n,f[e[i].n]));
            }
    }
    return;
}
int l[210000],r[210000];
int main()
{
    memset(head,-1,sizeof(head));
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&u,&v);
        if(~u)
        {
            add(i,u,0x3f3f3f3f);
            l[i]=ecnt-1;
        }
        if(~v)
        {
            add(i,v,0x3f3f3f3f);
            r[i]=ecnt-1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        if(v==1)
        {
            e[l[u]].v=i-1;
            e[l[u]^1].v=i-1;
        }
        else
        {
            e[r[u]].v=i-1;
            e[r[u]^1].v=i-1;
        }
    }
    dijk();
    for(int i=1;i<=n;i++)
        printf("%d\n",f[i]==0x3f3f3f3f?-1:f[i]);
    return 0;
}