首页 > 代码库 > 3027 - Corporative Network
3027 - Corporative Network
3027 - Corporative Network
思路:并查集;
cost记录当前点到根节点的距离,每次合并时路径压缩将cost更新。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<math.h> 6 #include<stack> 7 #include<set> 8 #include<queue> 9 using namespace std;10 int bin[20005];11 int du[20005];12 char str[20];13 int main(void)14 {15 int i,j;16 int n;17 scanf("%d",&n);18 while(n--)19 {20 int m;21 scanf("%d",&m);22 for(i = 1; i <= 20005; i++)23 bin[i] = i,du[i] = 0;24 while(scanf("%s",str),str[0]!=‘O‘)25 {26 int x,y;27 if(str[0]==‘I‘)28 {29 scanf("%d %d",&x,&y);30 int xx;31 for(xx = y; bin[xx]!=xx;)32 {33 xx = bin[xx];34 du[y]+=du[xx];35 }36 bin[y] = xx;37 bin[x] = xx;38 du[x] = du[y]+abs(x-y)%1000;39 }40 else41 { int sum = 0;42 int xx;scanf("%d",&x);43 for(xx = x; bin[xx]!=xx;)44 {45 xx=bin[xx],du[x]+=du[xx];46 }47 bin[x] = xx;48 printf("%d\n",du[x]);49 }50 }51 }52 return 0;53 }
3027 - Corporative Network
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。