首页 > 代码库 > LA 3027 合作网络
LA 3027 合作网络
https://vjudge.net/problem/UVALive-3027
题意：
有n个结点，初始时每个结点的父节点都不存在。你的任务是执行一次I操作和E操作，格式如下：
I u v：把结点u的父节点设为v，距离为|u-v|除以1000的余数。输入保证执行指令前u没有父节点。
E u：询问u到根结点的距离。
思路：
主要思想是并查集，记录一下每个结点到根结点的距离即可。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 const int maxn = 20000 + 5; 6 7 int p[maxn], d[maxn]; 8 int n; 9 char c;10 11 int find(int x)12 {13 if (p[x] != x)14 return d[x] + find(p[x]);15 else16 return d[x];17 }18 19 int main()20 {21 //freopen("D:\\txt.txt", "r", stdin);22 int T;23 scanf("%d", &T);24 while (T--)25 {26 memset(d, 0, sizeof(d));27 scanf("%d", &n);28 for (int i = 0; i <= n; i++)29 p[i] = i;30 int u, v;31 while (scanf("%c",&c) && c != ‘O‘)32 {33 if (c == ‘E‘)34 {35 scanf("%d", &u);36 int sum=find(u);37 cout << sum << endl;38 }39 else if (c == ‘I‘)40 {41 scanf("%d%d", &u, &v);42 p[u] = v;43 d[u] = abs(v - u) % 1000;44 }45 }46 }47 }
LA 3027 合作网络
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。