【题解】LuoGu3225：[HNOI2012]矿场搭建-CSDN博客

本文链接：https://blog.csdn.net/ModestCoder_/article/details/96719638

本文介绍了一种解决特定图论问题的算法思路，通过识别割点并将其从图中移除来划分联通块，进而根据不同情况计算方案数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
读题花了我好一会时间，看来我的语文阅读能力不够
这道题对于我这种小菜鸡还是有一点思维难度的

因为有些点会坍塌，不妨理解为把某个点删掉，那么是不是就想到了一个图论里的玩意——割点
先把割点求出，然后割掉，图变成了一堆联通块的集合
对于每个联通块，因为块的内部并没有割点，对于块直接相连的其他割点个数分类讨论

没有割点与块相连，必须随意选择两个点建立出口，块内部互相联通，如果只建一个出口，那么万一这个出口坍塌，那么整个块就完蛋了，所以随便选两个出口满足正确性，方案数为 $C_{sum}^{2}$ (sum为块中点个数)
有一个割点与块相连，只用随意选择一个出口。因为，若出口坍塌，可以通过割点跑到别的块；若其他点（包括割点）坍塌，可以跑到出口。方案数为 $s u m$
至少两个割点与块相连，则不用建出口，因为不管谁坍塌，总存在一个割点使你跑到其他块去

注意点：

多组数据，初始化
总点数n需要自己求
开longlong

Code：

#include <bits/stdc++.h>
#define maxn 1010
#define LL long long
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], Index, dfn[maxn], low[maxn], cut[maxn];
int vis[maxn], tot, cnt, ans1, n, m, Case;
LL ans2, sum;

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c=  getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge) { y, head[x] }; head[x] = num; }

void tarjan(int u, int fa){
	dfn[u] = low[u] = ++Index;
	int child = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (!dfn[v]){
			++child;
			tarjan(v, fa);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u] && u != fa) cut[u] = 1;
		}
		low[u] = min(low[u], dfn[v]);
	}
	if (u == fa && child >= 2) cut[u] = 1;
}

void dfs(int u){
	vis[u] = tot, ++sum;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (cut[v] && vis[v] != tot){
			++cnt; vis[v] = tot;
		}
		if (!vis[v]) dfs(v);
	}
}

void calc(int x){
	if (!x) ans1 += 2, ans2 *= sum * (sum - 1) / 2; else
	if (x == 1) ++ ans1, ans2 *= sum;
}

int main(){
	while (~scanf("%d", &m) && m){
		++Case,	n = 0, num = 0;
		memset(head, 0, sizeof(head));
		while (m--){
			int x = read(), y = read();
			addedge(x, y); addedge(y, x);
			n = max(n, max(x, y));
		}
		memset(cut, 0, sizeof(cut));
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		Index = 0;
		for (int i = 1; i <= n; ++i)
			if (!dfn[i]) tarjan(i, i);
		memset(vis, 0, sizeof(vis));
		tot = 0, ans1 = 0, ans2 = 1;
		for (int i = 1; i <= n; ++i)
			if (!vis[i] && !cut[i]){
				++tot; cnt = 0, sum = 0; dfs(i);
				calc(cnt);
			}
		printf("Case %d: %d %lld\n", Case, ans1, ans2);
	}
	return 0;
}