[题解]Codeforces Round #254 (Div. 2) B

链接：http://codeforces.com/contest/445/problem/B

描述：n种药品，m个反应关系，按照一定顺序放进试管中。如果当前放入的药品与试管中的药品要反应，危险系数变为之前的2倍；否则危险系数不改变。起始危险系数为1。求可能的最大的危险系数。

思路：遍历图

在图上画一画，就会发现，只要一块连通的图中的一个点放入后，之后每添加这块图中的一个点就会导致危险系数乘2。那么我们只需要找到一共有多少个连通图tmp，然后用总数减去得到ans。答案就是1LL<<ans。注意long long的位运算要记得在1后面加上LL！！！

我的实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define MaxN 60
 6 #define MaxM 1250
 7 typedef long long llt;
 8 struct node
 9 {
10     int v;
11     node *next;
12 };
13 node Edge[MaxM*2];
14 node *cnt=&Edge[0];
15 node *adj[MaxN];
16 bool vis[MaxN];
17 llt ans;
18 int n,m;
19 inline void Get_int(int &Ret)
20 {
21     char ch;
22     bool flag=false;
23     for(;ch=getchar(),ch<'0'||ch>'9';)
24         if(ch=='-')
25             flag=true;
26     for(Ret=ch-'0';ch=getchar(),ch>='0'&&ch<='9';Ret=Ret*10+ch-'0');
27     flag&&(Ret=-Ret);
28 }
29 inline void Addedge(int u,int v)
30 {
31     node *p=++cnt;
32     p->v=v;
33     p->next=adj[u];
34     adj[u]=p;
35 
36     p=++cnt;
37     p->v=u;
38     p->next=adj[v];
39     adj[v]=p;
40 }
41 void Read()
42 {
43     Get_int(n);Get_int(m);
44     int i,j,k;
45     for(i=1;i<=m;++i)
46     {
47         Get_int(j);Get_int(k);
48         Addedge(j,k);
49     }
50 }
51 llt Dfs(int u)
52 {
53     vis[u]=true;
54     llt Ret=1;
55     for(node *p=adj[u];p;p=p->next)
56         if(!vis[p->v])
57             Ret+=Dfs(p->v);
58     return Ret;
59 }
60 void Solve()
61 {
62     int i;
63     ans=0;
64     for(i=1;i<=n;++i)
65         if(!vis[i])
66             ans+=(Dfs(i)-1);
67     ans=1LL<<ans;
68     printf("%I64d
",ans);
69 }
70 int main()
71 {
72     Read();
73     Solve();
74     return 0;
75 }

View Code

效率：