洛谷2860 [USACO06JAN]冗余路径Redundant Paths

原题链接

题意实际上就是让你添加尽量少的边，使得每个点都在至少一个环上。

显然对于在一个边双连通分量里的点已经满足要求，所以可以用\(tarjan\)找边双并缩点。

对于缩点后的树，先讲下我自己的弱鸡做法，每次找直径，因为将直径改为环显然使得新添的边贡献最大，这样贪心的连下去，直到所有点满足要求为止。

而实际上有一个简单结论，该题答案就是缩点后树的叶子节点个数除\(2\)（向上取整）。

代码是用的我自己的弱鸡做法。

#include<cstdio>

using namespace std;

const int N = 5010;

const int M = 2e4 + 10;

int fi[N], di[M], ne[M], cfi[N], cdi[M], cne[M], dfn[N], low[N], bl[N], pre[N], l = 1, lc, ti, DCC, ma, ma_id;

bool bg[M], v[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 void add_c(int x, int y)

{

	cdi[++lc] = y;

	cne[lc] = cfi[x];

	cfi[x] = lc;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

void tarjan(int x, int la)

{

	int i, y;

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

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

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

		{

			tarjan(y, i);

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

			if (low[y] > dfn[x])

				bg[i] = bg[i ^ 1] = 1;

		}

		else

			if (i ^ la ^ 1)

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

}

void dfs(int x)

{

	int i, y;

	bl[x] = DCC;

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

		if (!bl[y = di[i]] && !bg[i])

			dfs(y);

}

void dfs_2(int x, int fa, int d)

{

	int i, y;

	if (ma < d)

	{

		ma = d;

		ma_id = x;

	}

	pre[x] = fa;

	for (i = cfi[x]; i; i = cne[i])

		if ((y = cdi[i]) ^ fa)

			dfs_2(y, x, v[x] && v[y] ? d : d + 1);

}

int main()

{

	int i, n, m, x, y, s = 0;

	n = re();

	m = re();

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

	{

		x = re();

		y = re();

		add(x, y);

		add(y, x);

	}

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

		if (!dfn[i])

			tarjan(i, 0);

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

		if (!bl[i])

		{

			DCC++;

			dfs(i);

		}

	for (i = 2; i <= l; i += 2)

	{

		x = bl[di[i ^ 1]];

		y = bl[di[i]];

		if (x ^ y)

		{

			add_c(x, y);

			add_c(y, x);

		}

	}

	while (DCC > 1)

	{

		ma = ma_id = 0;

		dfs_2(1, 0, 0);

		ma = 0;

		dfs_2(ma_id, 0, 0);

		for (i = ma_id; i; i = pre[i])

			if (!v[i])

			{

				v[i] = 1;

				DCC--;

			}

		s++;

	}

	printf("%d", DCC ^ 1 ? s : s ? s + 1 : s);

	return 0;

}

巴特西

洛谷2860 [USACO06JAN]冗余路径Redundant Paths

原题链接

最新文章

热门文章