题解 P1196 【[NOI2002]银河英雄传说】

Bill845514379 · 2019-08-14 22:41:27 · 题解

题意：

对于1到n的序列，有两种操作：
1. Mij,将i所在的队列加到j所在的队列中，当然是从后面加，保证原队列的顺序不变。
2. Cij，查找i和j之间有多少个数，当然如果ij不在一个队列中，输出-1就行。
  思路：

有队列合并，队列查询，并查集肯定少不了，但是如何求i和j有多少个数，这就要用到带权并查集了，另外开一个数组记录每个点到根节点之间的距离，len数组吧，最终答案就是 len[i]+len[j]-1 ，记得减一因为不包含两个端点。

这个带权并查集怎么写，很明显假如不用路径压缩，合并一次对这条链进行更新，还有查询是否在一个集合也是从头找到尾，这样的话会超时，复杂度是O(n^2)，n为3万，（实测路径压缩+记录路径，刚好能卡过，这样常数比较小而已，但如果加强数据上限还是会卡死的，~~有点玄（4e8的样子）~~）

最终正解就是，路径压缩，每次合并对当前根节点（注意不是合并后的根节点）进行修改，合并，当前根节点的距离+=要合并队列的长度。但是有个问题，当前队列后面节点到根节点的距离并没有变，还是原来的，这只是对当前根节点进行了修改。这个问题在find函数中解决，每次find就对这个点到根节点的距离进行更新（条件是这个点是第一次find，也就是这个时候他的路径还没有被压缩，即 ff[x]!=ff[ff[x]] ,当然如果是第二次find，路径已经压缩过了，他到根节点的距离是不会变的）， len[x]+=len[ff[x]] ，其实就是把刚刚对根节点增加的长度分配到每个子节点上（条件是使用find时，不使用find的子节点其实并没有分配，这也不影响最终的结果，就相当于按需分配）

//AC代码 ：带权并查集

#include<stdio.h>
#include<cmath>
using namespace std;
#define maxn 30005
#define INF 1000000005
#define ll long long
//dis表示i队列的长度，len表示i到根节点的距离
int ff[maxn],dis[maxn],len[maxn];

int find(int x)
{
    if(ff[x]==x)
        return x;
    int t=find(ff[x]);
    len[x]+=len[ff[x]];
    return ff[x]=t;
}

void read(int &x)
{
    x=0;
    bool flag=0;
    char ch=getchar();
    if(ch=='-') flag=1;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar();
    if(flag) x=-x;
}

int main()
{
    int n;
    read(n);
    for(int i=0; i<=maxn; i++)
        ff[i]=i,dis[i]=1;

    for(int i=0; i<n; i++)
    {
        char str;
        scanf(" %c",&str);
        int x,y;
        read(x),read(y);
        int nx=find(x);
        int ny=find(y);
        if(str=='M')
        {
            if(nx!=ny)
            {
                ff[nx]=ny;
                len[nx]+=dis[ny];
                dis[ny]+=dis[nx];
                dis[nx]=1;
            }
        }
        else
        {
            if(nx!=ny)
            {
                printf("-1\n");
                continue;
            }
            if(len[x]>len[y])
                printf("%d\n",len[x]-len[y]-1);
            else
                printf("%d\n",len[y]-len[x]-1);
        }
    }
    return 0;
}

 //刚开始还不会带权并查集，水过去的代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define maxn 30005
#define INF 1000000005
#define ll long long

int path[maxn];//记录路径
int ff[maxn],dis[maxn],out[maxn],len[maxn];
//out为i队列最外面的数字是什么

int find(int x)
{
    return x==ff[x]?x:ff[x]=find(ff[x]);
}

void read(int &x)
{
    x=0;
    bool flag=0;
    char ch=getchar();
    if(ch=='-') flag=1;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar();
    if(flag) x=-x;
}

int main()
{
    int n;
    read(n);
    for(int i=0; i<=maxn; i++)
        ff[i]=i,out[i]=i,dis[i]=1,path[i]=i;

    for(int i=0; i<n; i++)
    {
        char str;
        scanf(" %c",&str);
        int x,y;
        read(x),read(y);
        int nx=find(x);
        int ny=find(y);
        if(str=='M')
        {
            if(nx!=ny)
            {
                ff[nx]=ny;
                path[nx]=out[ny];
                int t=out[nx];
//对这条链的距离进行更新，所有值都更新了，所以慢啊
                while(t!=out[ny]) 
                {
                    len[t]+=dis[ny];
                    t=path[t];
                }
                out[ny]=out[nx];
                dis[ny]+=dis[nx];
                dis[nx]=1;
            }
        }
        else
        {
            if(nx!=ny)
                printf("-1\n");
            else
                printf("%d\n",abs(len[x]-len[y])-1);
        }

    }
    return 0;
}

题解 P1196 【[NOI2002]银河英雄传说】

题意：

思路：