网站开发教程下载,wordpress门户模板,企业管理系统项目经历,南安网站设计1 /*2 有N个企业#xff0c;每个企业想要实现通信#xff0c;要用线路来连接#xff0c;线路的长度为abs(a-b)%1000;3 如果企业a 链接到了企业b 那么b就是the center of the serving!4 然后有两种操作#xff1a;5 E a #xff1a; 输出企业a到serving ce… 1 /*2 有N个企业每个企业想要实现通信要用线路来连接线路的长度为abs(a-b)%1000;3 如果企业a 链接到了企业b 那么b就是the center of the serving!4 然后有两种操作5 E a 输出企业a到serving center 的线路的距离6 I a, b 将企业a连接到企业 b那么b就成为了serving center之前连接a的企业他们的serving center也变成了b 7 8 思路并查集 压缩路径时回溯求解 9 */
10 #includeiostream
11 #includecstring
12 #includecmath
13 #includecstdio
14 #define M 20005
15 using namespace std;
16 int n;
17 int f[M];
18 int ans[M];//节点 i到 serving center的距离
19
20 int getFather(int x){
21 if(xf[x]) return x;
22 int ffgetFather(f[x]);
23 ans[x]ans[f[x]];//节点x到serving center 的距离要加上其父节点到serving center的距离
24 return f[x]ff;
25 }
26
27 void Union(int a, int b){
28 if(ab) return;
29 f[a]b;
30 ans[a]abs(a-b) % 1000;
31 }
32
33 int main(){
34 int t;
35 char ch[3];
36 cint;
37 while(t--){
38 cinn;
39 int a, b;
40 memset(ans, 0, sizeof(ans));
41 for(int i1; in; i)
42 f[i]i;
43 while(cinch ch[0]!O){
44 if(ch[0]E){
45 cina;
46 getFather(a);
47 coutans[a]endl;
48 }
49 else{
50 cinab;
51 Union(a, b);
52 }
53 }
54 }
55 return 0;
56 } 转载于:https://www.cnblogs.com/hujunzheng/p/3902548.html
