版权说明：来自 石门ss学校 Guohao OJ ,禁止转载

题目描述

虽然小X不喜欢化学原理，但他特别喜欢把一大堆液体倒在一起。

现在小X有n种液体，其中m对会发生反应。现在他想把这n种液体按某种顺序倒入一个容器内，让他获得最刺激的体验，也就是使危险系数尽量大。

我们可以这样计算危险系数，一开始容器内没有任何液体，危险系数为1。每次液体倒入容器时，若容器内已有一种或多种液体会与这种液体发生反应，则危险系数会乘2，否则危险系数不变。

最大危险系数小X不会算，希望你帮帮他。

输入输出格式

输入格式：

第一行包含两个整数n，m。

接下来m行，每行包含两个整数a，b，表示液体a和液体b会发生反应。

输出格式：

一行，包含一个整数，表示最大危险系数。

输入输出样例

输入样例：

3 21 22 3

输出样例：

4

说明

数据规模：

对于30%的数据，n≤10；

对于100%的数据，1≤n≤1000，a≠b，同种反应不会出现多次。

 

题目分析：

通过题目可以发现，不用管放置的顺序，我们就可以轻而易举得想到并查集，将液体合并为后，一个集的危险指数就为  2 的 （集合内个数-1） ，最后将所有集合值加起来就是答案。

 

代码

1 #include
      
        2 #include
       
         3 using namespace std; 4 typedef string str; 5 const int Max_N=1e3+5; 6 int n,m; 7 int Fa[Max_N],tot[Max_N]; 8 string mul(string s1,string s2) 9 {10 //    一连串的高精度乘法，个人码风问题不建议借鉴11 //     最好自己手写一个12     #define len1 (s1.size())13     #define len2 (s2.size())14     int maxx=max(len1,len2);15     register int i,j,k,l;16     int Ans[maxx<<1|1];17     for(i=0;i<=(maxx<<1);i++)Ans[i]=0;18     for(i=0;i
        
         =0;i--,k++){21         for(j=len2-1,l=(maxx<<1)-k;j>=0;j--,l--)22             Ans[l]+=(int)s1[i]*s2[j];        23     }24     for(i=(maxx<<1);i>=0;i--)25         if(Ans[i]>9){26             int xy=Ans[i]/10;27             Ans[i-1]+=xy;28             Ans[i]%=10; 29         }30     int top=0;31     while(Ans[top]==0&&top^(maxx<<1))top++;32     string res;33     for(i=top;i<=maxx<<1;i++)res+=Ans[i]+'0';34     return res;35 }36 int Find(int p)37 {38 //    查询祖先39     if(Fa[p]==p)40         return p;41     return Fa[p]=Find(Fa[p]);42 }43 void megre(int u,int v)44 {45     Fa[Find(u)]=Fa[Find(v)];46     return ;47 }48 str Pow(str b,int p)49 {50 //    字符串版快速幂:-D51     if(!p)52         return "1";53     str res="1";54     while(p){55         if(p&1)56             res=mul(res,b);57         b=mul(b,b);58         p>>=1;59     }60     return res;61 }62 int main()63 {64     scanf("%d%d",&n,&m);65     int u,v;66     register int i,j;67     for(i=1;i<=n;i++)    68         Fa[i]=i;69     for(i=1;i<=m;i++){70         scanf("%d%d",&u,&v);71         megre(u,v);//²¢²é¼¯ºÏ²¢²Ù×÷ 72     }        73     for(i=1;i<=n;i++)74         tot[Find(i)]++;//统计集合内个数75     str res="1";76     for(i=1;i<=n;i++)77         if(tot[i]>1)78             res=mul(res,Pow("2",tot[i]-1));79 //    答案为集合内的 pow(2,(集合内个数-1)) 的和80     cout<
        
       
      

 

写在最后的话：

题解仅供思路，要想成为 dalao ，请学会并尽量会做到教他人甚至自己写题解。

博主（目前）是一名初二蒟蒻，如有问题还请大家指出，一起交流学习！

Happy every day!　　　　　　　　——2019.4.11