题目
[hnoi2012]矿场搭建
解析
这个题做的我十分自闭。。
没看出这个是个点双,然后一晚上+半上午。。
一看肯定和割点有关,我们找到所有的点双,会发现有这么几种情况
- 连通块中一个割点也没有,这时我们至少要建两个出口,以防万一某个出口塌了就gg了,方案的话就从size(联通块大小)个点中随便选两个,也是(dbinom{size}{2})个。
- 联通块中有一个割点,如果这个割点塌了就gg了,需要一个出口,但如果塌的不是割点,我们可以通过割点跑到另一个连通块中,所以只需要割点。根据乘法原理,方案数只需要乘上这个连通块的size。
- 联通块中大于两个割点的时候,若一个割点塌了,可以通过另一个割点跑到另一个联通块里,所以不需要再加出口。
需要注意的是
题目中没有给出具体多少个点,但应该是连续的,因为我按连续的做的
代码
#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); } }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603269.html