首页 > 代码库 > UVALive 3027（并查集）
UVALive 3027（并查集）
题意：某公司的各企业群要建立联系，I i j 表示企业i与企业j建立联系，并且以企业j为中心(并查集中的父亲)(企业j为暂时的中心企业)，E i 表示查询企业 i 距离此时的中心企业的距离。各企业间的距离规定：企业i 与 企业j 间距离为|i - j| % 1000。
分析：改造并查集中的find函数，每次查询i企业到中心企业的距离时，不断向上依次寻找他的父亲，直到找到中心企业为止，不断累加现企业与其父亲企业间的距离即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<cctype> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 #include<sstream> 8 #include<iterator> 9 #include<algorithm>10 #include<string>11 #include<vector>12 #include<set>13 #include<map>14 #include<deque>15 #include<queue>16 #include<stack>17 #include<list>18 #define fin freopen("in.txt", "r", stdin)19 #define fout freopen("out.txt", "w", stdout)20 #define pr(x) cout << #x << " : " << x << " "21 #define prln(x) cout << #x << " : " << x << endl22 typedef long long ll;23 typedef unsigned long long llu;24 const int INT_INF = 0x3f3f3f3f;25 const int INT_M_INF = 0x7f7f7f7f;26 const ll LL_INF = 0x3f3f3f3f3f3f3f3f;27 const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;28 const double pi = acos(-1.0);29 const double EPS = 1e-6;30 const int dx[] = {0, 0, -1, 1};31 const int dy[] = {-1, 1, 0, 0};32 const ll MOD = 1e9 + 7;33 const int MAXN = 20000 + 10;34 const int MAXT = 10000 + 10;35 using namespace std;36 int fa[MAXN];37 int ans;38 int find(int v)39 {40 ans += abs(fa[v] - v) % 1000;41 if(fa[v] == v)42 return fa[v];43 else find(fa[v]);44 }45 int main()46 {47 int T;48 scanf("%d", &T);49 while(T--)50 {51 int N;52 scanf("%d", &N);53 char c;54 for(int i = 1; i <= N; ++i)55 fa[i] = i;56 while(scanf("%c", &c) == 1)57 {58 if(c == ‘O‘) break;59 if(c == ‘E‘)60 {61 int x;62 scanf("%d", &x);63 ans = 0;64 int t = find(x);65 printf("%d\n", ans);66 }67 else if(c == ‘I‘)68 {69 int a, b;70 scanf("%d%d", &a, &b);71 fa[a] = b;72 }73 }74 }75 return 0;76 }
UVALive 3027（并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。