【BZOJ2730】【HNOI2012】礦場搭建（點雙，割點）

Description

煤礦工地可以看成是由隧道連接配接挖煤點組成的無向圖。為安全起見，希望在工地發生事故時所有挖煤點的勞工都能有一條出路逃到救援出口處。于是礦主決定在某些挖煤點設立救援出口，使得無論哪一個挖煤點坍塌之後，其他挖煤點的勞工都有一條道路通向救援出口。

請寫一個程式，用來計算至少需要設定幾個救援出口，以及不同最少救援出口的設定方案總數。

Solution

上次寫點雙還是在暑假，，早就忘了怎麼寫了。。。于是重學了一遍。

（下面的割點都是指的原圖的割點而不是點雙的割點，而且點雙根本就沒有割點啊）

對于每一個點雙，如果沒有割點，那麼需要建2個出口，炸了一個還有一個

如果有一個割點，隻要在任意一個非割點處建1個出口即可，炸了出口可以走到其他點雙，炸了其它點可以從出口出去。

如果有很多割點，那麼不需要建出口。

Code

/************************************************
 * Au: Hany01
 * Date: Apr 5th, 2018
 * Prob: [BZOJ2730][HNOI2012] 礦場搭建
 * Email: [email protected]
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read()
{
	register int _, __; register char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 505, maxm = 1005;

int n, m, e, v[maxm], nex[maxm], beg[maxn], dfn[maxn], low[maxn], tim, bccs, co[maxn], iscut[maxn];
stack<PII> stk;
PII tmp;
vector<int> bcc[maxn];

inline void add(int uu, int vv) { v[++ e] = vv, nex[e] = beg[uu], beg[uu] = e; }

void dfs(int u, int fa)
{
	register int chs = 0;
	dfn[u] = low[u] = ++ tim;
	for (register int i = beg[u]; i; i = nex[i]) if (v[i] != fa)
	{
		tmp = mp(u, v[i]);
		if (!dfn[v[i]]) {
			stk.push(tmp), ++ chs;
			dfs(v[i], u), chkmin(low[u], low[v[i]]);
			if (low[v[i]] >= dfn[u])
			{
				iscut[u] = 1;
				++ bccs, bcc[bccs].clear();
				for ( ; ; ) {
					tmp = stk.top(), stk.pop();
					if (co[tmp.x] != bccs) co[tmp.x] = bccs, bcc[bccs].pb(tmp.x);
					if (co[tmp.y] != bccs) co[tmp.y] = bccs, bcc[bccs].pb(tmp.y);
					if (u == tmp.x && v[i] == tmp.y) break;
				}
			}
		} else if (dfn[v[i]] < dfn[u])
			stk.push(tmp), chkmin(low[u], dfn[v[i]]);
	}
	if (!fa && chs == 1) iscut[u] = 0;
}

inline LL C2(LL n) { return n * (n - 1) / 2; }

inline void calc()
{
	int Ans = 0;
	LL Sum = 1;
	For(i, 1, bccs)
	{
		register int cnt = 0;
		rep(j, SZ(bcc[i])) cnt += iscut[bcc[i][j]];
		if (!cnt) Ans += 2, Sum *= C2(SZ(bcc[i]));
		else if (cnt == 1) ++ Ans, Sum *= SZ(bcc[i]) - 1;
		//cout << cnt << ' ' << SZ(bcc[i]) << endl;
	}
	printf("%d %lld\n", Ans, Sum);
}

int main()
{
#ifdef hany01
	File("bzoj2730");
#endif

	static int Case = 0, uu, vv;
	while (scanf("%d", &m), m)
	{
		//Clear
		n = e = tim = bccs = 0, Set(beg, 0), Set(dfn, 0), Set(iscut, 0), Set(co, 0);
		while (!stk.empty()) stk.pop();

		//Input
		while (m --)
			uu = read(), vv = read(),
			add(uu, vv), add(vv, uu), chkmax(n, max(uu, vv));

		//Get cut vertexs and BCCs
		For(i, 1, n) if (!dfn[i]) dfs(i, 0);

		//Statistic
		printf("Case %d: ", ++ Case);
		calc();
	}

    return 0;
}
//悲莫悲生離别，樂莫樂新相識，兒女古今情。
//    -- 辛棄疾《水調歌頭·壬子三山被召陳端仁給事飲餞席上作》