Solution

输入中没有出现过的矿场点是不用考虑的，所以不用考虑只有一个点的点双联通分量。

要使某个挖矿点倒塌，相当于割去这个点，所以我们求一遍割点和点双联通分量。

之后的点双联通分量构成一棵树。树上的节点有两种情况

1：仅有一条边（仅有一个割点在内部）—— 相当与叶子节点，把它与父亲节点相连的割点割去后，必须在里面设一个逃生出口

2：大于一条边（有大于一个割点在内部）——割去其中一个割点时，还可以通过另一个割点到达逃生出口，所以不用设置。

所以我们要求的就是在所有仅含一个割点的点双联通分量内设置一个逃生出口，并根据乘法原理计算方案数。

特别的：当整个图是一个点双连通图时，设置任意两个逃生出口即可。

Code

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 #define rd read()

 #define R register

 #define ll long long

 using namespace std;

 const int N = 1e3;

 int head[N], tot;

 int dfn[N], low[N], col_num;//col_num为点双联通分量个数

 int n, m, mark[N], cut[N], rt, maxn, cut_num[N];//cut_num为点双联通分量内的割点数

 int st[N], tp, cnt;

 ll ans1, ans2;

 vector<int> q[N];

 struct edge {

     int nxt, to, fr;

 }e[N << ];

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 void add(int u, int v) {

     e[++tot].to = v;

     e[tot].nxt = head[u];

     e[tot].fr = u;

     head[u] = tot;

 }

 void tarjan(int u) {

     dfn[u] = low[u] = ++cnt;

     st[++tp] = u;

     int flag = ;

     for(R int i = head[u]; i; i = e[i].nxt) {

         R int nt = e[i].to;

         if(!dfn[nt]) {

             tarjan(nt);

             low[u] = min(low[u], low[nt]);

             if(low[nt] >= dfn[u]) {

                 col_num++;

                 flag ++;

                 if(flag >  || u != rt)

                     cut[u] = ;

                 for(; tp;) {

                     int z = st[tp--];

                     q[col_num].push_back(z);

                     if(z == nt) break;

                 }

                 q[col_num].push_back(u);

             }

         } else low[u] = min(low[u], dfn[nt]);

     }

 }

 void init() {

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

         q[i].clear();

     ans1 = maxn = col_num = cnt = tot = ;

     ans2 = ;

     memset(dfn, , sizeof(dfn));

     memset(mark, , sizeof(mark));

     memset(cut, , sizeof(cut));

     memset(low, , sizeof(low));

     memset(head, , sizeof(head));

     memset(cut_num, , sizeof(cut_num));

 }

 int main()

 {

     for(int T = ; ; T++) {

         n = rd;

         if(!n) return ;

         init();

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

             int u = rd, v = rd;

             add(u, v); add(v, u);

             mark[u] = mark[v] = ;

             maxn = max(maxn, u);

             maxn = max(maxn, v);

         }

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

             if(!dfn[i] && mark[i]) tarjan(rt = i);

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

             for(int j = , len = q[i].size(); j < len; ++j) {

                 if(cut[q[i][j]]) cut_num[i]++;

             }

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

                 if(cut_num[i] == ) ans1++, ans2 = ans2 * (int)(q[i].size() - );

         printf("Case %d: %lld %lld\n", T, ans1 ? ans1 : , ans1 ? ans2 : (int)(q[].size() - ) * q[].size()/ );

     }

 }

秒客网

BZOJ2730 [HNOI2012]矿场搭建 - Tarjan割点

Solution

Code

相关文章