codeforces 445B. DZY Loves Chemistry 解题报告

题目链接：http://codeforces.com/problemset/problem/445/B

题目意思：给出 n 种chemicals，当中有 m 对可以发生反应。我们用danger来评估这些chemicals的厉害程度。厉害程度是这样的：一瓶什么都不加的瓶子的danger 为 1，如果有一对（即 m = 1）chemicals 能够发生反应，那么这个danger就会加倍（1*2）。不过要注意一点，对于 1 2； 1 3； 2 3，danger为 4 而不为 8。（因为这个条件限制了：if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2）。现在就要问，如何安排放入的顺序，使得这个danger值最大。

对于此次比赛的题目，我真心觉得B题出得好咯，因为我不会做咯，呵呵呵......不过没事，我参考别人算是学会了。

tag说分类是：dfs and similar dsu

但是我觉得用并查集来做更容易理解些（差不多一年前学的东西了= =）。整体思路就是先预处理，将每个点的祖先都设为自己，初始化ans值为 1 << n，表示它有n个连通分量，然后根据 m 组数据连边，连通分量要减少，因为连边了嘛，最后统计有多少个连通分量，每得到一个连通分量，即代码中的find(i) == i，ans 就除以2.

以下是test 4 和 test 5 的书面模拟操作。

test 4

(1) 连边（2）简化后变为：

test 5

最后得到的连通分量只有5个，所以ans从 1 << 20 要除以5次，即 ans >>= 1 计算5次。

　具体代码如下：

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 using namespace std;

 typedef long long LL;

 const int maxn =  + ;

 int n, m, x, y, fa[maxn];

 int find(int x)

 {

     while (x != fa[x])

         x = fa[x];

     return x;

 }

 int main()

 {

     while (scanf("%d%d", &n, &m) != EOF)

     {

         for (int i = ; i <= n; i++)

             fa[i] = i;

         while (m--)

         {

             scanf("%d%d", &x, &y);

             int fa_x = find(x);

             int fa_y = find(y);

             fa[fa_x] = fa_y;    // 合并集合

         }

         LL ans = (1LL << n);

         for (int i = ; i <= n; i++)

         {

             if (find(i) == i)

                 ans >>= ;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

巴特西

codeforces 445B. DZY Loves Chemistry 解题报告

最新文章

热门文章