题解 P5295 [北京省选集训2019]图的难题
_sys
·
·
题解
给定一张图，你需要选出一个子集，使得这个子集没有环，子集的补集没有环。
***
一张图是合法的当且仅当其所有导出子图 $(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)$。
```cpp
#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;
}
```