鏈接

F -?秋實(shí)大哥打游戲 Time Limit:1000MS?????Memory Limit:65535KB?????64bit IO Format:%lld & %llu Submit?Status?Practice?UESTC 1070 Appoint description:?System Crawler? (2016-04-24)

Description

”也許人生就是游戲，你卻執(zhí)意耕耘著春秋。” —— 秋實(shí)大哥嘆道。

秋實(shí)大哥是一個(gè)喜歡玩游戲的人，相較于其他種類的游戲，秋實(shí)大哥更喜歡自由開(kāi)放的沙盒游戲，尤其是minecraft。

現(xiàn)在，秋實(shí)大哥發(fā)現(xiàn)了N個(gè)獨(dú)立的小島（編號(hào)1,2,3…..N)，于是他要把這些小島連起來(lái)。

每一次，秋實(shí)大哥會(huì)選擇兩個(gè)不同的小島x（x是所在集合的中心）和y（y不一定是集合的中心），如果小島x和小島y不在一個(gè)集合里，就建立一條距離為|x?y|?mod?1000的邊，

把這兩片小島合并為一個(gè)新的集合，中心為y原來(lái)所在的集合中心。

但，秋實(shí)大哥想實(shí)時(shí)知道某一個(gè)小島距當(dāng)前所在集合中心的距離。由于秋實(shí)大哥忙著過(guò)節(jié)，所以他想請(qǐng)你幫忙。

Input

第一行有一個(gè)整數(shù)N表示小島的個(gè)數(shù)。

接下來(lái)有若干行，每一行為以下兩種操作中的一種：

I x y : 表示秋實(shí)大哥想要在x和y之間建立一條邊。 E x : 詢問(wèn)x到當(dāng)前集合中心的距離。

輸入以一個(gè)大寫(xiě)字母O結(jié)束。

1≤N≤100000，操作數(shù)≤200000。

Output

對(duì)于每一次詢問(wèn)，輸出一個(gè)整數(shù)，即x到當(dāng)前集合中心的距離，占一行。

Sample Input

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

Sample Output

1?
3

要求：復(fù)習(xí)時(shí)重做一遍

#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];//在路徑壓縮之前保存連接的邊，否則路徑壓縮后直接指向根節(jié)點(diǎn)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;//這個(gè)初始化非常重要，好好想想 }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; }

　　分析：寫(xiě)的第一道帶權(quán)并查集，還是挺有意思的，跟普通并查集比起來(lái)就是邊多了權(quán)值，

抓住核心式子，dis[child ?to ?par ?]+=dis[par to ? root]，以兒子和父親間合并的那條邊為橋梁

轉(zhuǎn)載于:https://www.cnblogs.com/smilesundream/p/5440246.html

總結(jié)

以上是生活随笔為你收集整理的CDOJ 1070 秋实大哥打游戏 带权并查集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。