CodeforcesRound#254(Div.2)

Note In the first sample, there's only one way to pour, and the danger won't increase. In the second sample, no matter we pour the 1 st chemical first, or pour the 2 nd chemical first, the answer is always 2 . In the third sample, there ar

Note

In the first sample, there's only one way to pour, and the danger won't increase.

In the second sample, no matter we pour the 1 st chemical first, or pour the 2 nd chemical first, the answer is always 2 .

In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).

写给自己:水水的题目, 竟然WA,一直找不到错误的地方. 最后才发现思路和细节都没有错,只是答案 输出的类型精度不够(应该用long long 的只用了int).多么痛的领悟.出来献丑,不忘耻辱.

分析: 把各种化学物品的反应关系画成图, 可知只要用任一种遍历图(这个图可能是非连通的)的方法(DFS,BFS,并查集均可)遍历它便可求解(存在一条边则danger翻倍).

如下使用"邻接矩阵表示的DFS":

#include 
#include 
#define maxn 55
int G[maxn][maxn],vis[maxn];
int n;
long long ans;
void DFS(int v)
{
    int w;
    vis[v]=1;
    for(w=1;w 

另外, 借鉴别人并查集的做法:

查看更多关于CodeforcesRound#254(Div.2)的详细内容...