c/c++语言开发共享[HNOI2012]矿场搭建 (点双连通)

题目

[hnoi2012]矿场搭建

解析

这个题做的我十分自闭。。
没看出这个是个点双，然后一晚上+半上午。。
一看肯定和割点有关，我们找到所有的点双，会发现有这么几种情况

1. 连通块中一个割点也没有，这时我们至少要建两个出口，以防万一某个出口塌了就gg了，方案的话就从size（联通块大小）个点中随便选两个，也是(dbinom{size}{2})个。
2. 联通块中有一个割点，如果这个割点塌了就gg了，需要一个出口，但如果塌的不是割点，我们可以通过割点跑到另一个连通块中，所以只需要割点。根据乘法原理，方案数只需要乘上这个连通块的size。
3. 联通块中大于两个割点的时候，若一个割点塌了，可以通过另一个割点跑到另一个联通块里，所以不需要再加出口。

需要注意的是
题目中没有给出具体多少个点，但应该是连续的，因为我按连续的做的

代码

#include <bits/stdc++.h> #define int long long using namespace std; const int n = 1e6 + 10; int n, m, js, cnt, num, sum, size, tot, ans1, ans2; /*  js计数器      sum联通块编号     tot联通块中割点个数     size联通块中点的个数      ans1第一问答案     ans2第二问答案  */ int head[n], dfn[n], low[n], bel[n]; bool cut[n], vis[n]; class node {     public :         int v, nx; } e[n];  template<class t>inline void read(t &x) {     x = 0; int f = 0; char ch = getchar();     while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();     while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();     x = f ? -x : x;     return; }  inline void add(int u, int v) {     e[++num].nx = head[u], e[num].v = v, head[u] = num; }  void tarjan(int u, int fa) {     dfn[u] = low[u] = ++cnt;     int child = 0;     for (int i = head[u]; ~i; i = e[i].nx) {         int v = e[i].v;         if (!dfn[v]) {             tarjan(v, u);             low[u] = min(low[u], low[v]);             if (low[v] >= dfn[u] && u != fa) cut[u] = 1, vis[u] = 1;             if (u == fa) child++;         }         low[u] = min(low[u], dfn[v]);     }     if (child >= 2 && u == fa) cut[u] = 1, vis[u] = 1; }  void dfs(int u) {     vis[u] = 1;     size++;     for (int i = head[u]; ~i; i = e[i].nx) {         int v = e[i].v;         if (!vis[v] && !cut[v]) dfs(v);     //没有被访问过且不是割点          if (cut[v] && bel[v] != sum) bel[v] = sum, tot++;   //用来标记割点在哪个连通块内      } }  signed main() {     while (scanf("%lld", &n) && n) {         num = cnt = m = ans1 = 0;         ans2 = 1;         memset(e, 0, sizeof (e));         memset(dfn, 0, sizeof (dfn));         memset(low, 0, sizeof (low));         memset(cut, 0, sizeof (cut));         memset(vis, 0, sizeof (vis));         memset(bel, 0, sizeof (bel));         memset(head, -1, sizeof (head));         for (int i = 1, x, y; i <= n; ++i) {             read(x), read(y);             add(x, y), add(y, x);             m = max(m, max(x, y));         }         for (int i = 1; i <= m; ++i) if (!dfn[i]) tarjan(i, i);         for (int i = 1; i <= m; ++i) {             if (vis[i] || cut[i]) continue;             tot = size = 0;             sum++;             dfs(i);             if (tot == 0) ans1 += 2, ans2 *= ((size - 1) * size) >> 1;             if (tot == 1) ans1++, ans2 *= size;         }         printf("case %lld: %lld %lldn", ++js, ans1, ans2);     } }