P3225 [HNOI2012]矿场搭建【割点 + 求点双 + 简单组合数】

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

输入文件有若干组数据，每组数据的第一行是一个正整数 N（N<=500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

输出格式

输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

输入输出样例

输入 #1

输出 #1

Case 1: 2 4
Case 2: 4 1

说明/提示

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；

Case 2 的一组解为(4,5,6,7)。

思路

　　通过读题和观察样例我们可以知道这道题是和割点有关的。

　　通过tarjan可以求出所有的 DCC，然后分情况讨论。

　　如果一个点双里有 >= 2 个割点，那么不管哪里炸了都可以通过没炸的割点去往其他的点双，所以这种点双是不需要加出口的。

　　如果只有一个割点，那么只要割点炸了，点双里的点就只能在内部找出口，所以这种 dcc 里一定要有一个出口。

　　如果没有割点，那么这种连通块只要保证有两个出口，不管哪个炸了都能走另一个出口来保证一定能出去。

　　然后简单计算组合数即可。

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6 const int maxn = 510 + 7;
  7 
  8 int head[maxn], dfn[maxn], low[maxn];
  9 int cnt = 0, tot = 0, tim = 0, top = 1, n, cl = 0, k;
 10 int vis[maxn];
 11 int color[maxn];
 12 int iscut[maxn];
 13 int cas[maxn][5];
 14 vector<int> dcc[maxn];///存点双
 15 
 16 /*
 17 head[],结构体edge:存边
 18 
 19 dfn[],low[]:tarjan中数组
 20 
 21 st[]:模拟栈
 22 
 23 out[]:出边
 24 
 25 sd[]:强连通分量存储
 26 
 27 dq[]:统计答案
 28 */
 29 
 30 template<class T>inline void read(T &res)
 31 {
 32     char c;T flag=1;
 33     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 34     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 35 }
 36 
 37 struct Edge{
 38     int nxt, to;
 39 }edge[maxn * 2];
 40 
 41 inline void BuildGraph(int from, int to)
 42 {
 43     cnt++;
 44     edge[cnt].to = to;
 45     edge[cnt].nxt = head[from];
 46     head[from] = cnt;
 47 }
 48 
 49 stack<int> s;
 50 
 51 void tarjan(int x)
 52 {
 53     int fa = 0;
 54     s.push(x);
 55     low[x] = dfn[x] = ++tim;
 56     for ( int i = head[x]; i; i = edge[i].nxt ) {
 57         int v = edge[i].to;
 58         if(!dfn[v]) {
 59             tarjan(v);
 60             low[x] = min(low[x], low[v]);
 61             if(low[v] >= dfn[x]) {
 62                 ++fa, ++k;
 63                 if(x != 1 || fa > 1) {
 64                     iscut[x] = 1;
 65                     //dbg(x);
 66                 }
 67                 dcc[k].push_back(x);
 68                 int now = 0;
 69                 do {
 70                     now = s.top();
 71                     s.pop();
 72                     dcc[k].push_back(now);
 73                 } while (now != v);
 74             }
 75         }
 76         else {
 77             low[x] = min(low[x], dfn[v]);
 78         }
 79     }
 80 }
 81 
 82 void init() {
 83     cnt = 0;
 84     cl = 0;
 85     tim = 0;
 86     k = 0;
 87     while(!s.empty()) {
 88         s.pop();
 89     }
 90     for ( int i = 1; i <= maxn; ++i ) {
 91         dcc[i].clear();
 92     }
 93     memset(vis, 0, sizeof(vis));
 94     memset(dfn, 0, sizeof(dfn));
 95     memset(low, 0, sizeof(low));
 96     memset(iscut, 0, sizeof(iscut));
 97     memset(edge, 0, sizeof(edge));
 98     memset(head, 0, sizeof(head));
 99 }
100 
101 int main() 
102 {
103     int cas = 0;
104     while(scanf("%d",&n) && n) {
105         
106         init();
107         for ( int i = 1; i <= n; ++i ) {
108             int x, y;
109             scanf("%d %d",&x, &y);
110             BuildGraph(x, y);
111             BuildGraph(y, x);
112             
113         }
114         for ( int i = 1; i <= n; ++i ) {
115             if(!dfn[i]) {
116                 tarjan(i);
117             }
118         }
119         LL ans1 = 0, ans2 = 1;
120         for ( int i = 1; i <= k; ++i ) {
121             int v1 = dcc[i].size(), v2 = 0;///v2割点个数
122             for ( int j = 0; j < v1; ++j ) {
123                 v2 += iscut[dcc[i][j]];
124                 //dbg(v2);
125             }
126             if(v2 == 1) {
127                 ans1++;
128                 ans2 *= v1 - 1;
129                 //dbg(ans2);
130             }
131             if(v2 == 0) {
132                 ans1 += 2;
133                 ans2 *= v1 * (v1 - 1) / 2;
134                 //dbg(ans2);
135             }
136         }
137         printf("Case %d: ",++cas);
138         printf("%lld %lld
",ans1, ans2);
139     }
140     return 0;
141 }

View Code