BZOJ2730或洛谷3225 [HNOI2012]矿场搭建

BZOJ原题链接

洛谷原题链接

显然在一个点双连通分量里，无论是哪一个挖煤点倒塌，其余挖煤点就可以互相到达，而对于一个点双连通分量来说，与外界的联系全看割点，所以我们先用\(tarjan\)求出点双连通分量，再对每个点双进行讨论。

若该点双不含割点，那么这个点双是与外面隔绝的，至少要设置两个出口。
若该点双只含一个割点，那么这个点双只有经过割点才能到达外面，若割点倒塌，则与外面隔绝，所以需要设置一个出口。
若该点双含两个及以上的割点，那么无论哪一个点倒塌，这个点双依旧能到达外面，所以不需要设置出口。

最后根据乘法原理，将每个点双需要建立的出口个数乘起来即是总方案数。

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

const int N = 510;

const int M = 1010;

int fi[N], di[M], ne[M], dfn[N], low[N], sta[N], l, tp, ti, r, DCC;

bool ct[N];

vector<int>po[N];

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y)

{

	di[++l] = y;

	ne[l] = fi[x];

	fi[x] = l;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

inline int maxn(int x, int y)

{

	return x > y ? x : y;

}

void tarjan(int x)

{

	int i, y, g = 0, z;

	dfn[x] = low[x] = ++ti;

	sta[++tp] = x;

	for (i = fi[x]; i; i = ne[i])

		if (!dfn[y = di[i]])

		{

			tarjan(y);

			low[x] = minn(low[x], low[y]);

			if (dfn[x] <= low[y])

			{

				g++;

				if (x ^ r || g > 1)

					ct[x] = 1;

				DCC++;

				po[DCC].clear();

				do

				{

					z = sta[tp--];

					po[DCC].push_back(z);

				} while (z ^ y);

				po[DCC].push_back(x);

			}

		}

		else

			low[x] = minn(low[x], dfn[y]);

}

int main()

{

	int i, j, n, m, x, y, o, k, t = 0;

	long long s_1, s_2;

	while (1)

	{

		t++;

		m = re();

		if (!m)

			return 0;

		n = l = ti = DCC = s_1 = 0;

		s_2 = 1;

		memset(fi, 0, sizeof(fi));

		memset(dfn, 0, sizeof(dfn));

		memset(low, 0, sizeof(low));

		memset(ct, 0, sizeof(ct));

		for (i = 1; i <= m; i++)

		{

			x = re();

			y = re();

			add(x, y);

			add(y, x);

			n = maxn(n, maxn(x, y));

		}

		for (i = 1; i <= n; i++)

			if (!dfn[i])

			{

				if (!fi[i])

				{

					po[++DCC].push_back(i);

					continue;

				}

				tarjan(r = i);

			}

		for (i = 1; i <= DCC; i++)

		{

			for (j = 0, k = 0, o = po[i].size(); j < o; j++)

				if (ct[po[i][j]])

					k++;

			if (!k)

			{

				s_1 += 2;

				s_2 *= 1LL * o * (o - 1) >> 1;

			}

			else

				if (k && k < 2)

				{

					s_1++;

					s_2 *= (o - k);

				}

		}

		printf("Case %d: %lld %lld\n", t, s_1, s_2);

	}

	return 0;

}

巴特西

BZOJ2730或洛谷3225 [HNOI2012]矿场搭建

BZOJ原题链接

洛谷原题链接

最新文章

热门文章