最大闭合子图学习笔记 / P2805 [NOI2009] 植物大战僵尸

最大闭合子图是网络流中的一个小分支，感觉有点冷门。但是实际上却非常有用。

前置知识：最大流，最大流最小割定理。

一个子图是否是闭合的有这样的定义：对于这个子图里面的点的所有的出边，不存在一条出边到达的点在子图外。

最大闭合子图就是在一个带点权的有向图的闭合子图中点权和最大的一个方案。

显然环（更加严谨的，强连通分量）一定是闭合的，所以我们可以考虑将环缩点，将原图变成一个 DAG，这样显然会更加好一点。

---

那么问题就变成了如何对一个 DAG 求最大闭合子图。这里我们配合网络流来求解。

首先讲结论：

• 第一步：建立虚点 $S$ 为超源点，$T$ 为超汇点。
• 第二步：连边。
  • 循环所有的点的点权 $a_x$：
    • 如果 $a_x\ge 0$，则从 $S$ 连一条出边，终点为 $x$，容量为 $a_x$。
    • 如果 $a_x<0$，则从 $x$ 连一条出边，终点为 $T$，容量为 $-a_x$。
  • 对于原图中的边对应的点对（缩点之后的点也算点）$(i,j)$，从 $i$ 连一条终点为 $j$ 边权为 $+\infty$ 的边。
• 第三步：求解答案。
  • 设正点权之和为 $sum$，设 $S\to T$ 的最大流（也就是最小割）为 $f$，则最大闭合子图的点权和为 $sum-f$。

---

证明就直接搬图片了，懒得打：

注明一下出处：胡伯涛的那篇叫做《最小割模型在信息学竞赛中的应用》的论文。

P2805 [NOI2009] 植物大战僵尸

进入了讲题环节。

题意感觉虽然比较繁杂，但还是比较好懂的。

首先一开始不一定会想到网络流，先分析题目。

首先写出每一个点的权值，然后不难想到植物之间存在“保护关系”，所以考虑建图连边，如果 $x$ 保护 $y$ 则连一条 $x\to y$ 的边：

然后就会想到一件事：一个环根本就不需要考虑，因为这个环根本就不可能被僵尸入侵！

所以考虑使用拓扑排序来找环，找到的环上的点统统删去。但是还需要注意这种情况：如果这个强连通分量并不是在最左边，则其左边的植物仍然不可能被入侵（因为必须要先入侵右边的，而右边的入侵不了），也要删掉：

然后最终就变成了若干个 DAG。然后考虑建反边，就变成了求最大闭合子图，做完了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
const int N = 610;
vector<int> v[N];
int val[N], inv[N];
bool f[N];struct edge {int to, val;int id;
};
vector<edge> g[N];
int d[N];void bfs(int s) {memset(d, -1, sizeof d);queue<int> q;q.push(s), d[s] = 0;while (!q.empty()) {int u = q.front();q.pop();for (auto [i, val, id] : g[u])if (d[i] == -1 && val > 0)d[i] = d[u] + 1, q.push(i);}
}
int cur[N];int dfs(int u, int t, int fl) {if (u == t)return fl;for (int i = cur[u]; i < (int)g[u].size(); i = ++cur[u])if (d[g[u][i].to] == d[u] + 1 && g[u][i].val > 0) {int x = dfs(g[u][i].to, t, min(fl, g[u][i].val));if (x > 0) {g[u][i].val -= x, g[g[u][i].to][g[u][i].id].val += x;return x;} elsed[g[u][i].to] == -1;}return 0;
}int dinic(int s, int t) {int ans = 0;while (1) {bfs(s);if (d[t] == -1)return ans;memset(cur, 0, sizeof cur);int x = 0;while ((x = dfs(s, t, 9e18)) > 0)ans += x;}return ans;
}void add(int x, int y, int w) {g[x].push_back({y, w, (int)g[y].size()});g[y].push_back({x, 0, (int)g[x].size() - 1});
}//前面都是板子signed main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {int cnt = 0;cin >> val[(i - 1)*m + j] >> cnt;while (cnt--) {int x, y;cin >> x >> y;v[(i - 1)*m + j].push_back(x *m + y + 1), inv[x * m + y + 1]++;}if (j > 1)v[(i - 1) * m + j].push_back((i - 1) * m + j - 1), inv[(i - 1) * m + j - 1]++;//连边，保护关系}queue<int> q;for (int i = 1; i <= n * m; i++)if (!inv[i])q.push(i);while (!q.empty()) {int u = q.front();q.pop();for (auto i : v[u])if ((--inv[i]) == 0)q.push(i);}//拓扑排序找环for (int i = 1; i <= n * m; i++)if (inv[i])for (int j = 1; j <= (i - 1) % m + 1; j++)f[(i - 1) / m * m + j] = 1;int sum = 0;for (int i = 1; i <= n * m; i++)if (!f[i]) {for (auto j : v[i])if (!f[j])add(j, i, 1e15);//这里需要建反边if (val[i] >= 0)add(n * m + 1, i, val[i]), sum += val[i];elseadd(i, n * m + 2, -val[i]);//连边，求最大闭合子图}cout << max(0ll, sum - dinic(n *m + 1, n *m + 2)) << endl;return 0;
}