[题解]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\n",ans);

69 }

70 int main()

71 {

72     Read();

73     Solve();

74     return 0;

75 }

效率：

巴特西

[题解]Codeforces Round #254 (Div. 2) B - DZY Loves Chemistry

最新文章

热门文章