題目鏈接:

http://acm.uestc.edu.cn/#/problem/show/1070

題意:

題解:

帶權并查集
每次往上更新的時候，順便把邊權更新了就好
記住得路徑壓縮

代碼:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 // 16 const int maxn = 1e5+10; 17 18 int fa[maxn]; 19 ll w[maxn]; 20 21 int find(int x){ 22 if(fa[x] == x) return x; 23 24 find(fa[x]); 25 w[x] += w[fa[x]]; 26 fa[x] = find(fa[x]); 27 return fa[x]; 28 } 29 30 void Union(int v,int u){ 31 int t1 = find(v), t2 = find(u); 32 if(t1 == t2) return ; 33 fa[v] = t2; 34 w[v] = abs(u-v) % 1000 + w[u]; 35 } 36 37 int main(){ 38 int n=read(); 39 for(int i=0; i<=n; i++){ 40 fa[i] = i; 41 w[i] = 0; 42 } 43 char op; 44 while(scanf(" %c",&op) && op!='O'){ 45 if(op=='I'){ 46 int v,u; scanf("%d%d",&v,&u); 47 Union(v,u); 48 }else{ 49 int x=read(); 50 find(x); 51 printf("%lld\n",w[x]); 52 } 53 } 54 55 return 0; 56 }

?

轉載于:https://www.cnblogs.com/yxg123123/p/6827649.html

總結

以上是生活随笔為你收集整理的cdoj 1070 秋实大哥打游戏　带权并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。