首页 > 代码库 > [NOI2002]银河英雄传说

[NOI2002]银河英雄传说

2024-10-03 14:27:39   217人阅读

OJ题号：洛谷1196

思路：加权并查集。

对于每个联通块，记录最后（权值最大）的“战舰”。然后按照加权并查集的基本套路合并。最后输出两艘“战舰”权值之差。

 1 #include<iostream> 2 #include<algorithm> 3 const int N=30001; 4 class UnionFindSet { 5     private: 6         int anc[N],w[N],end[N]; 7         int Find(int x) { 8             if(x==anc[x]) return x; 9             int t=Find(anc[x]);10             w[x]+=w[anc[x]];11             return anc[x]=t;12         }13     public:14         UnionFindSet() {15             for(int i=1;i<N;i++) {16                 anc[i]=end[i]=i;17                 w[i]=0;18             }19         }20         void Union(int x,int y) {21             int t=Find(x);22             w[t]=1;23             anc[t]=end[Find(y)];24             end[Find(y)]=end[t];25         }26         int Query(int x,int y) {27             return (Find(x)==Find(y))?std::abs(w[x]-w[y])-1:-1;28         }29 };30 UnionFindSet set;31 int main() {32     std::ios_base::sync_with_stdio(false);33     int t;34     std::cin>>t;35     while(t--) {36         char op;37         int x,y;38         std::cin>>op>>x>>y;39         if(op==‘M‘) {40             set.Union(x,y);41         }42         else {43             std::cout<<set.Query(x,y)<<std::endl;44         }45     }46     return 0;47 }

 

[NOI2002]银河英雄传说


联系
我们