CDOJ 1070 秋实大哥打游戏 带权并查集

链接

F - 秋实大哥打游戏

Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%lld & %llu

Submit Status Practice UESTC 1070

Appoint description: 
System Crawler  (2016-04-24)

Description

”也许人生就是游戏，你却执意耕耘着春秋。” —— 秋实大哥叹道。

秋实大哥是一个喜欢玩游戏的人，相较于其他种类的游戏，秋实大哥更喜欢自由开放的沙盒游戏，尤其是minecraft。

现在，秋实大哥发现了N个独立的小岛（编号1,2,3…..N)，于是他要把这些小岛连起来。

每一次，秋实大哥会选择两个不同的小岛x（x是所在集合的中心）和y（y不一定是集合的中心），如果小岛x和小岛y不在一个集合里，就建立一条距离为|x−y| mod 1000的边，

把这两片小岛合并为一个新的集合，中心为y原来所在的集合中心。

但，秋实大哥想实时知道某一个小岛距当前所在集合中心的距离。由于秋实大哥忙着过节，所以他想请你帮忙。

Input

第一行有一个整数N表示小岛的个数。

接下来有若干行，每一行为以下两种操作中的一种：

I x y : 表示秋实大哥想要在x和y之间建立一条边。

E x : 询问x到当前集合中心的距离。

输入以一个大写字母O结束。

1≤N≤100000，操作数≤200000。

Output

对于每一次询问，输出一个整数，即x到当前集合中心的距离，占一行。

Sample Input

3 
I 1 2 
E 1 
I 3 1 
E 3 
O

Sample Output

1

要求：复习时重做一遍

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long LL;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int maxn=100000;

char s[5];

int f[maxn+10],dis[maxn+10];

int findr(int x)

{

     if(f[x]!=x)

        {

            int par=f[x];//在路径压缩之前保存连接的边，否则路径压缩后直接指向根节点

            f[x]=findr(f[x]);//递归

            dis[x]+=dis[par];

        }

     return f[x];

}

void unite(int x,int y)

{

    int ry=findr(y);

    if(x==ry) return;

    f[x]=y;//建立一条边

    dis[x]=abs(x-y)%1000;//这个初始化非常重要，好好想想

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        for(int i=1;i<=n;i++) {f[i]=i;dis[i]=0;}

        while(~scanf("%s",s))

        {

            int x,y;

            if(s[0]=='I')

               {

                    scanf("%d %d",&x,&y);

                    unite(x,y);

               }

            else if(s[0]=='E')

            {

                scanf("%d",&x);

                findr(x);

                printf("%d\n",dis[x]);

            }

            else break;

        }

    }

    return 0;

}

　　分析：写的第一道带权并查集，还是挺有意思的，跟普通并查集比起来就是边多了权值，

抓住核心式子，dis[child  to  par  ]+=dis[par to   root]，以儿子和父亲间合并的那条边为桥梁