最大权闭合子图
引入
闭合子图指对于子图 \(G=(V,E)\)，\(\forall u \in V, (u,v)\in E\)，都有 \(v\in V\)。
最大权闭合子图无非就是对于所有的闭合子图 \(G\) 中 \(\sum_{u\in V} w_u\) 最大的闭合子图。
对于这个图中，闭合子图有哪些呢？
红色框圈画出的即为 \(1\) 个闭合子图，因为对于任意一个点所连向的点都在该子图内。
主算法
不难发现任意一个割所划分成的 \(2\) 个集合均为闭合子图，而我们要求最大权闭合子图，故考虑如何求解。
建立一个流网络，将源点向所有权值为正的点连一条长度为该点权值的边，将所有权值为负数的点向汇点连一条长度为该点权值的绝对值的边。对于原图中的边，在流网络中均为 \(+\infty\)。
对于割 \([S,T]\)，\(c(S,T)=\sum_{(u,v)\in E,u\in S,v\in T}c(u,v)\)，由于中间的边权均为 \(+\infty\)，所以只会割两边的边，即 \(c(S,T)=\sum_{(s,v)\in E,v\in T}c(s,v)+\sum_{(u,t)\in E,u\in S}c(u,t)\)。
又因为建图的时候 \(s\) 所连向的边，均为连向点的边权；而连向 \(t\) 的边的边权均为连向他点的权值。故，\(c(S,T)=\sum_{(s,v)\in E,v\in T}c(s,v)+\sum_{(u,t)\in E,u\in S}c(u,t)=\sum_{(s,v)\in E,v\in T}w_v-\sum_{(u,t)\in E,u\in S}w_u\)
考虑最大权闭合子图的权值为什么？\(val=\sum_{(s,v)\in E,v\in S}w_v+\sum_{(u,t)\in E,u\in S}w_u\)。
不难发现第二项是完全一样的：所以将 \(c(S,T)\) 与 \(val\) 相加得，\(c(S,T)+val=\sum_{(s,v)\in E,v\in T}w_v+\sum_{(s,v)\in E,v\in S}w_v\)
由于 \(S\) 与 \(T\) 共同构成了点集 \(V\)，故 \(\sum_{(s,v)\in E,v\in T}w_v+\sum_{(s,v)\in E,v\in S}w_v=\sum_{(s,v)\in E}w_v=\sum_{w_v>0}w_v\)
综上所述，\(val=\sum_{w_v>0}w_v-c(S,T)\)，通过数学知识推理得 \(c(S,T)\) 应最小，即求最小割。
P4174 [NOI2006] 最大获利
模版题，按照上述做法建图即可。
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 6e4 + 10, M = 4e5 + 10, INF = 1e18;
int n, m, s, t;
int a[N], b[N];
int h[N], e[M], ne[M], f[M], idx;
int dist[N], cur[N];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
memset(dist, -1, sizeof dist);
queue<int> q;
q.emplace(s), dist[s] = 0, cur[s] = h[s];
while (q.size()) {
auto u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (dist[v] == -1 && f[i]) {
dist[v] = dist[u] + 1, cur[v] = h[v];
if (v == t) return 1;
q.emplace(v);
}
}
}
return 0;
}
int find(int u, int lim) {
if (u == t) return lim;
int flow = 0;
for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
cur[u] = i;
int v = e[i];
if (dist[v] == dist[u] + 1 && f[i]) {
int tmp = find(v, min(f[i], lim - flow));
if (!tmp) dist[v] = -1;
flow += tmp, f[i] -= tmp, f[i ^ 1] += tmp;
}
}
return flow;
}
int dinic() {
int res = 0, flow;
while (bfs()) while (flow = find(s, INF)) res += flow;
return res;
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
memset(h, -1, sizeof h);
s = 0, t = n + m + 1;
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 1; i <= m; i ++) {
int u, v;
cin >> u >> v >> b[i];
add(i + n, u, INF), add(i + n, v, INF);
}
int tot = 0;
for (int i = 1; i <= m; i ++)
add(s, i + n, b[i]), tot += b[i];
for (int i = 1; i <= n; i ++)
add(i, t, a[i]);
cout << tot - dinic() << endl;
return 0;
}
最大密度子图
引入
定义无向图 \(G=(V,E)\) 的密度为 \(\frac{|E|}{|V|}\)。则，对于一个无向图 \(G=(V,E)\)，令 \(G\) 的子图 \(G'=(V',E')\)，满足 \(\forall (u,v)\in E', u\in V',v\in V'\)。对于所有满足条件的子图 \(G\) 中，密度最大的即为最大密度子图。
主算法
对于形式 \(\frac{|E|}{|V|}\)，不难想到通过分数规划求解，即二分 \(g\)，如果 \(\frac{|E|}{|V|}\ge g\)，则说明 \(g\) 还可以更大，调整二分左端点；反之，调整二分右端点。
将式子继续化简可以得到：\(|E|-g|V|\ge 0\)，也就是求 \(|E|-g|V|\) 的最大值，即 \(g|V|-|E|\) 的最小值。
最小割是可以解决点集的，但是难以算出边数的多少。所以，考虑如何将边数加入割。
考虑红色圈出的子图，如何计算边数呢？可以考虑使用度数，某个点度数减去该点连向集合外部的边的个数再除 \(2\)，即可得到集合内边的个数，即 \(\frac{\sum_{u\in V}d_u-c(V,\bar V)}{2}\)。这样，就与割产生了关系。
继续推式子：\(g|V|-|E|=\sum_{u\in V}g-\frac{\sum_{u\in V}d_u-c(V,\bar V)}{2}=\sum_{u\in V}(g-\frac{d_u}{2})+\frac{c(V,\bar V)}{2}\)
为了使与最小割有单调关系，将割 \(c(V,\bar V)\) 的系数提出得 \(\frac{\sum_{u\in V}(2g-d_u)+c(V,\bar V)}{2}\)
那么，就可以建图了。对于任意一个点 \(u\) 均向汇点 \(t\) 连一条边权为 \(2g-d_u\) 的边，不过由于 \(2g-d_u\) 可能会小于 \(0\)，所以边权应为 \(2g-d_u+U\)，其中 \(U\) 为常数。对于点之间的边，即为原图的边，为了算边数所以边权均为 \(1\)。源点 \(s\) 向任意一个点连一条边权为 \(U\) 的边即可。\(U\) 取 \(|E|\) 即可，因为 \(d_u\) 不可能超过 \(|E|\)。下图为一个例子。
建完图后，由于部分边权多加了 \(U\)，所以考虑新图最小割 \(c'(S,T)\) 与 \(|E|-g|V|\) 的关系。令 \(P=S-\{s\},P'=\bar P - \{t\}\)，则最小割的边集分为 \(4\) 种情况：\(P\rightarrow \{t\},\{s\}\rightarrow P',P\rightarrow P',\{s\}\rightarrow \{t\}\)。不过，最后一种边不存在舍去。
\[\begin{aligned} c'(S,T)=&\sum_{u\in P} (U+2g-d_u)+\sum_{v\in P'}U+\sum_{u\in P}\sum_{v\in P'}c(u,v)\\ =&\sum_{u\in P}(U+2g-d_u+\sum_{v\in P'}c(u,v))+\sum_{v\in P'}U\\ =&\sum_{u\in P}(U+2g-(d_u-\sum_{v\in P'}c(u,v)))+\sum_{v\in P'}U\\ =&\sum_{u\in P}(U+2g-\sum_{v\in P}c(u,v))+\sum_{v\in P'}U\leftarrow u\ 所有出边-向集合外边=向集合内边\\ =&\sum_{u\in P}2g-\sum_{u\in P}\sum_{v\in P}c(u,v)+\sum_{v\in P'}U+\sum_{v\in P}U\\ =&|P|2g+ 2|E|+U\cdot n\\ \end{aligned} \]故，\(|E|-g|V|=\frac{U\cdot n-c'(S,T)}{2}\)，这里 \(V\) 与 \(P\) 等价，都是我们选出的点。到此，该问题得以解决。
POJ3155 - Hard Life
模版题，使用上述做法建图计算即可。
对于输出方案，选择的集合其实就是最小割中 \(S\) 集合，那么怎么找出呢？只需要从 \(s\) 每次走 \(>0\) 的边所能到达的点的集合，便是答案（注意：不能包含 \(s\)）。
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e2 + 10, M = 3e3 + 10;
const double eps = 1e-6;
int n, m, s, t;
int h[N], e[M], ne[M], idx;
double f[M];
int d[N], cur[N], dg[N], st[N];
vector<int> res;
std::vector<PII> E;
void add(int a, int b, double c1, double c2) {
e[idx] = b, ne[idx] = h[a], f[idx] = c1, h[a] = idx ++;
e[idx] = a, ne[idx] = h[b], f[idx] = c2, h[b] = idx ++;
}
bool bfs() {
memset(d, -1, sizeof d);
queue<int> q;
q.emplace(s), d[s] = 0, cur[s] = h[s];
while (q.size()) {
int u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (d[v] == -1 && f[i] > 0) {
d[v] = d[u] + 1, cur[v] = h[v];
if (v == t) return 1;
q.emplace(v);
}
}
}
return 0;
}
double find(int u, double lim) {
if (u == t) return lim;
double flow = 0;
for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
cur[u] = i;
int v = e[i];
if (d[v] == d[u] + 1 && f[i] > 0) {
double tmp = find(v, min(lim - flow, f[i]));
if (tmp <= 0) d[v] = -1;
f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
}
}
return flow;
}
void build(double g) {
memset(h, -1, sizeof h);
idx = 0;
for (auto v : E) add(v.fi, v.se, 1, 1);
for (int i = 1; i <= n; i ++) add(s, i, m, 0);
for (int i = 1; i <= n; i ++) add(i, t, 2.0 * g - dg[i] + m, 0);
}
bool dinic(double g) {
build(g);
double res = 0, flow;
while (bfs()) while (flow = find(s, 1e18)) res += flow;
return res < m * n * 1.0;
}
void dfs(int u) {
if (u != s) res.emplace_back(u);
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (!st[v] && f[i] > 0) dfs(v);
}
}
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
s = 0, t = n + 1;
for (int i = 1; i <= m; i ++) {
int u, v;
cin >> u >> v;
E.emplace_back(u, v), dg[u] ++, dg[v] ++;
}
double l = 0, r = m;
while (r - l > eps) {
double mid = (l + r) * 0.5;
if (dinic(mid)) l = mid;
else r = mid;
}
dinic(l), dfs(s);
if (!res.size()) {
cout << "1\n1";
return 0;
}
cout << res.size() << endl;
sort(res.begin(), res.end());
for (auto v : res)
cout << v << endl;
cout << endl;
return 0;
}