本文主要是介绍带权并查集 La 3027，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接 ： http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4075
每参考题解的时候其实我已经自己模拟把并查集改为带权并查集了
但是因为取模弄错 WA了几个小时。。。。。。。。。。。。
其实在回溯的时候，修改权值就行，然后查询之前，还需要再维护一次
先贴我的垃圾代码，好TMD冗杂：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>using namespace std;#define MAXN 20010
#define MOD 1000int father[MAXN],dis[MAXN];void makeset(int n)
{for(int i=0;i<=n;i++){father[i]=i;dis[i]=0;}
}inline int ABS(int a,int b)
{if(a-b>0)return a-b;else return b-a;
}int Find1(int x)
{if(x != father[x]){int t = Find1(father[x]);dis[x]+=dis[father[x]];father[x] =t;return father[x];}elsereturn x;
}void Union(int x, int y)
{/*调用Union之前必须先确定x,y不在同一个集合，然后把x的父节点改为y*/dis[x]=ABS(x,y)%MOD;int t=Find1(y);dis[y]+=dis[t];dis[x]+=dis[y];y=t;father[x]=y;
}int main()
{//freopen("La 3027.txt","r",stdin);int n,ncase,u,v;char c;scanf("%d",&ncase);while(ncase--){scanf("%d",&n);makeset(n);while(1){while((c=getchar()) != 'O' && c != 'E' && c != 'I');if(c == 'O')break;if(c == 'E'){scanf("%d",&u);Find1(u);printf("%d\n",dis[u]);}else{if(c == 'I'){scanf("%d%d",&u,&v);Union(u,v);//dis[u]=(ABS(u,v))%MOD;//father[u]=v;}}}}return 0;
}
然后看了刘汝佳的代码 果然大牛，比我的代码短了一半......
// LA3027 Corporative Network
// Rujia Liu
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;const int maxn = 20000 + 10;
int pa[maxn], d[maxn];int findset( int x ) {if (pa[x] != x) {int root = findset( pa[x] );d[x] += d[pa[x]];return pa[x] = root; } else return x;
}int main() {int T;cin >> T;while(T--) {int n, u, v;string cmd;cin >> n;for(int i = 1; i <= n; i++) { pa[i] = i; d[i] = 0; }while(cin >> cmd && cmd[0] != 'O') {if(cmd[0] == 'E') { cin >> u; findset(u); cout << d[u] << endl; }if(cmd[0] == 'I') { cin >> u >> v; pa[u] = v; d[u] = abs(u-v) % 1000; }}}return 0;
}这篇关于带权并查集 La 3027的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
