自动搬运

查看原文

来自洛谷，原作者为

	_sys goodbye, OI

搬运于2025-08-24 22:09:12，当前版本为作者最后更新于2021-07-05 15:49:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给定一张图，你需要选出一个子集，使得这个子集没有环，子集的补集没有环。

$T \leq 10$，$n \leq 500$，$m \leq 10^3$。

一张图是合法的当且仅当其所有导出子图 $(V, E)$ 满足 $|E| \leq 2|V|-2$。

必要性显然。充分性考虑归纳法。我们通过点数为 $|V|-1$ 的图成立推出点数为 $|V|$ 的成立。

设 $d(u)$ 表示 $u$ 的度数，我们取 $d$ 最小的一个作为我们加入的点 $u$。

那么 $1 \leq d(u) \leq 3$。否则 $\sum d=4|V|$，$|E|=2|V|$，不满足条件。

若 $d(u) \leq 2$，我们设相邻的点为 $v_1, v_2$，把 $(v_1, u)$ 加入第一个森林，$(v_2, u)$ 加入第二个森林，仍然满足性质。

若 $d(u)=3$，设相邻的点为 $v_1, v_2, v_3$。那么去掉 $u$ 及其邻边的所有图 $G$ 满足 $|E|<2|V|-2$。

我们考虑三个导出子图 $H_1(E_1, V_1)$, $H_2(E_2, V_2)$, $H_3(E_3, V_3)$，$H_1$ 不包含 $(u, v_1)$ 但包含 $v_2, v_3$，$H_2$ 不包含 $(u, v_2)$ 但包含 $v_1, v_3$，$H_3$ 不包含 $(u, v_3)$ 但包含 $v_1, v_2$。这样的 $H_1, H_2, H_3$ 有很多种。但至少有一个 $i$ 满足不存在 $H_i$ 使得 $|E_i|=2|V_i|-2$。

引理：若 $G_1(E_1, V_1), G_2(E_2, V_2)$ 满足 $|E_1|=2|V_1|-2, |E_2|=2|V_2|-2$，则 $G_1 \cap G_2(E'_1, V'_1), G_1 \cup G_2(E'_2, V'_2)$ 满足 $|E_1'|=2|V_1'|-2, |E_2'|=2|V_2'|-2$。因为交 + 并 = 和，假如一个没达到上界，另一个就要超过上界。

使用反证法，若三个 $H$ 都能达到上界，那他们的并也达到了上界，而他们的并，就是 $G$。矛盾。

那么假设 $H_1$ 达不到上界，那么我们在 $H_1$ 中加入一条边 $(v_2, v_3)$，这样 $H'_1$ 也是合法的。

于是我们考虑这样一张图：在 $(V, E)$ 的基础上，除去 $u$ 的出边，加入 $(v_2, v_3)$，根据归纳假设，它能够分成两个森林。

我们设第一个森林包含了 $(v_2, v_3)$，那么我们把这条边删去，加入 $(u, v_2), (u, v_3)$，它还是一个森林。第二个森林加入 $(u, v_1)$，它还是一个森林。

原命题得证。

也就是说，我们只用判断这张图是否满足对于所有的子图满足 $|E| \leq 2|V|-2$。

也就是说，$\max\{|E|-2|V|\} \leq -2$。

这是一个最大权闭合子图的模型。考虑一条边的权值为 $1$，一个点的权值为 $-2$，我们要求的是最大权闭合子图。

但是有一个问题！这个子图必须非空，因为空的图被判定为不合法了。

所以我们钦定一个点一定被选，把它在网络流中的点删去，最后把答案直接 $-2$ 即可。

这样的复杂度是 $O(nm \sqrt n)$ 的。

（好像这样就能过了，但是 uoj 那题就过不了）

考虑优化，发现每次是删一条边后的最大流。使用退流即可。

时间复杂度：$O(nm)$。

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 12005;
int T, n, m, ct, cnt, s, t, ans, cur[Maxn], dis[Maxn], head[Maxn];
struct edg
{
	int nxt, to, w;
} edge[10 * Maxn];
void add(int x, int y, int w)
{
	edge[++cnt] = (edg){head[x], y, w};
	head[x] = cnt;
	edge[++cnt] = (edg){head[y], x, 0};
	head[y] = cnt;
}
queue <int> Qu;
bool bfs(void)
{
	Qu.push(s);
	memset(dis, 0, sizeof(int[ct + 1]));
	while (!Qu.empty())
	{
		int u = Qu.front();
		Qu.pop();
		if (u == t)
		{
			while (!Qu.empty()) Qu.pop();
			return true;
		}
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			int to = edge[i].to;
			if (to != s && !dis[to] && edge[i].w) dis[to] = dis[u] + 1, Qu.push(to);
		}
	}
	return false;
}
int dfs(int u, int mini)
{
	if (u == t || !mini) return mini;
	int w, used = 0;
	for (int & i = cur[u]; i; i = edge[i].nxt)
	{
		int to = edge[i].to;
		if (dis[to] == dis[u] + 1 && edge[i].w)
		{
			w = dfs(to, min(mini - used, edge[i].w));
			edge[i].w -= w, edge[((i - 1) ^ 1) + 1].w += w, used += w;
			if (used == mini) return used;
		}
	}
	return used;
}
void dinic(int w)
{
	while (bfs())
	{
		memcpy(cur, head, sizeof(int[ct + 1]));
		ans += w * dfs(s, 0x3f3f3f3f);
	}
}
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		cnt = ans = 0;
		memset(head, 0, sizeof(int[ct + 1]));
		scanf("%d%d", &n, &m);
		ct = n;
		s = ++ct, t = ++ct;
		for (int i = 1; i <= n; i++)
			add(i, t, 2);
		for (int i = 1; i <= m; i++)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			++ct;
			add(s, ct, 1);
			add(ct, x, 0x3f3f3f3f), add(ct, y, 0x3f3f3f3f);
		}
		dinic(1);
		for (int i = 1; i <= 2 * n; i += 2)
		{
			s = (i + 1) / 2, t = n + 1, dinic(-1);
			edge[i].w = 0;
			s = n + 1, t = n + 2, dinic(1);
			if (m - ans >= 1)
			{
				puts("No");
				goto END;
			}
			edge[i].w = 2;
		}
		puts("Yes");
		END:;
	}
	return 0;
}