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

· · 题解

羞涩，其实这道题我看了题解才过的……
好叭，说说我的思想

这一题明显要用并查集，因为维护队列接龙的时候要用到记录父亲等等操作
而因为每一次输出的时候要输出i-j之间的战舰和
所以我们引入两个数组

那么，我们就可以尝试着去打程序了。

find找爸爸函数：

int find(int x)//找x的爸爸
{
    if(fat[x]==x)//如果找到根节点，这我就不多说了
        return x;
    int t1=fat[x],t2=find(fat[x]);//t1是它的父亲，t2是它父亲的父亲
    //（爷爷？滑稽）
    fat[x]=t2;//更新fat[x]的值
    toh[x]+=toh[t1];
    /*划重点！因为我们压缩了路径，所以这个点到父亲的距离
    要加上新压缩的路径中未计算的点*/
    return t2;//返回找到的父亲
}

unionn合并函数

void unionn(int r1,int r2)
{
    int f1=find(r1),f2=find(r2);//直接把根节点插上，不多说
    fat[f2]=f1;//记录父亲
    toh[f2]=sum[f1];//这里到以下全是重点！
    //原队列长度即是此节点到父亲的距离
    sum[f1]+=sum[f2];//f1队列后放了sum[f2]个战舰
    sum[f2]=0;//原队列清空
}

下面是AC code:

#include <cstdio>
#include <iostream>
using namespace std;
int sum[30001],fat[30001],toh[30001],t,ans;
int find(int x)
{
    if(fat[x]==x)
        return x;
    int t1=fat[x],t2=find(fat[x]);
    fat[x]=t2;
    toh[x]+=toh[t1];
    return t2;
}
void unionn(int r1,int r2)
{
    int f1=find(r1),f2=find(r2);
    fat[f2]=f1;
    toh[f2]=sum[f1];
    sum[f1]+=sum[f2];
    sum[f2]=0;
}
int abs(int op)
{
    return op<0?-op:op;
}
int main()
{
    char ds;
    int u,v;
    for(int i=1;i<=30000;i++)
    {
        fat[i]=i;
        sum[i]=1;
    }
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        cin>>ds;scanf("%d %d",&u,&v);
        if(ds=='M')
        {
            unionn(v,u);
        }
        else
        {
            if(find(u)!=find(v))
                printf("-1\n");
            else
                printf("%d\n",abs(toh[u]-toh[v])-1);
        }
    }
}

END.蒟蒻%%%dalao！