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 #include<iostream> 11 #include<cstring> 12 #include<cmath> 13 #include<cstdio> 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(x==f[x]) return x; 22 int ff=getFather(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(a==b) 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 cin>>t; 37 while(t--){ 38 cin>>n; 39 int a, b; 40 memset(ans, 0, sizeof(ans)); 41 for(int i=1; i<=n; ++i) 42 f[i]=i; 43 while(cin>>ch && ch[0]!='O'){ 44 if(ch[0]=='E'){ 45 cin>>a; 46 getFather(a); 47 cout<<ans[a]<<endl; 48 } 49 else{ 50 cin>>a>>b; 51 Union(a, b); 52 } 53 } 54 } 55 return 0; 56 }

?

轉載于:https://www.cnblogs.com/hujunzheng/p/3902548.html

總結

以上是生活随笔為你收集整理的hdu1962Corporative Network带权回路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。