小 X 的液體混合

題目大意：

在一個玻璃瓶里，放入一些液體，某一對液體放在一起會有反應(yīng)，當(dāng)某個液體有反應(yīng)時危險度就會乘2（初值為1），問危險度最大是多少

原題：

解題思路：

記錄下每一個點的根節(jié)點，然后并查集，最后輸出n減去根節(jié)點是自己的點（無法產(chǎn)生反應(yīng)的），就可以了

代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,x,y,sum,fathx,fathy,a[350],father[1005]; int fa(int dep)//并查集 {if (father[dep]==dep) return dep;//自己是根節(jié)點return fa(father[dep]);//往父節(jié)點搜 } void gjc() {int t=0;for (int i=1;i<=310;++i){a[i]=a[i]*2+t;//高精乘t=a[i]/10;a[i]%=10;} } int main() {scanf("%d %d",&n,&m);for (int i=1;i<=n;++i)father[i]=i;for (int i=1;i<=m;++i){scanf("%d %d",&x,&y);fathx=fa(x);//記錄根節(jié)點fathy=fa(y);//根節(jié)點father[min(fathx,fathy)]=max(fathx,fathy);//把序號小的液體記為序號大的液體的父親}for (int i=1;i<=n;++i)if (father[i]==i)//自己是根節(jié)點sum++;a[1]=1;//預(yù)處理for (int i=1;i<=n-sum;++i)//2的n-sum次方gjc();int k=310;//高精輸出while (!a[k]&&k>0) k--;for (int i=k;i>0;--i)printf("%d",a[i]); }

總結(jié)

以上是生活随笔為你收集整理的【并查集】小 X 的液体混合的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。