这是一道最大点权闭合图的问题，有论文最小割模型在信息学竞赛中的应用（%%）。这类问题的解法是建图转化成最小割问题，再用最大流求解。这篇论文里讲的很好，我这里基本按照原文思路进行证明。如果有时间和兴趣建议通读上面推荐的论文。
首先定义闭合图。闭合图是指一个图$G$，满足：若点$u$在$G$中，那么从$u$可达的所有点$v$也在$G$中。
建图：除开题目所给的点之外，再建立源点$s$和汇点$t$。记题目输入的图为$G_0(V_0,E_0)$，按如下规则建立图$G(V, E )$：
$$ \begin{cases} \langle s,u\rangle=w[u] \in E & u\in V_0,w[u] > 0,\\ \langle u,t\rangle=-w[u] \in E & u\in V_0,w[u] < 0,\\ \langle u,v\rangle=+\infty\in E & \langle u,v\rangle\in E_0.\end{cases} $$
这样处理之后，由于原图中的边权值都变成了正无穷，所以最小割中的边要么与$s$相连，要么与$t$相连。称这样的割为简单割。
下面证明，有向图中简单割和闭合图可以建立一一对应关系（数学中称为同构）。
下面的证明不知道思路乱不乱，建议结合那篇论文一起食用。他的证明比较简短，如果哪里搞不懂再回来看这里的证明。
先证明一个闭合图必存在一个简单割与之对应（闭合图对应简单割）。
思路：考虑图$G$的闭合子图$G'(V',E')$，由定义，其中一定没有指向$G'$外的边。那么$G_0$中对应的子图$G_0'$中，流出$G_0'$的一定是直接流出到t的边。为了切断$s$与$u$的联系，可以考虑将$G_0'$流出的边集$O$纳入割中。记$G_0'$的补图为$\overline{G_0'}$，那么现在只要防止流量从$\overline{G_0'}$流出。由于从$s$流进$G_0'$的边只可能从$O$流出，所以不必考虑它们，只要考虑从$s$流进$\overline{G_0'}$的边集$I$。显然$O\cup I$删除后，可以切断s与t的联系。
证明1（$O\cup I$是割）：割的定义：对某个顶点集合$S\subset V$，从$S$出发指向$S$外部的那些边的集合。在这里取$S=V'\cup\{s\}$。对$u\in S$，若$u=s$，从$u$出发指向$S$外部的边集即是$I$；若$u\in V'$，从$u$出发指向$S$外部的边集即是$O$。从而由定义，$O\cup I$是割。（还有事实：由于$s$不会直接向$t$连边，$O\cap I=\varnothing$）
再证明一个简单割必对应一个闭合图。
思路：希望仿照上面的构造方法，将简单割对应回闭合图，即寻找逆映射。设简单割$[S,T]$中与$s$相连的边集为$I$，与$t$相连的边集为$O$，那么这个割$[S, T]$对应的$S$应当是：（删掉简单割$[S,T]$中的边后，从$s$可达的点的集合）（记作$V'=S-\{s\}$）$\cup \{s\}$。下面证明这些点恰恰构成上面证明中提到的闭合图。
证明2（$V'$中的点及由$V'$出发的边集构成闭合图）由于$[S,T]$是割，删去$[S,T]$后，从$s$可达的点（一定在$S$中）一定无法离开$S$（找到指向$S$外的路径），由定义这些点是闭合图。若$V'$中有负权点，那么它指向$t$的边应当已被包含在$[S,T]$中。由于$[S,T]$是简单割，$V'$指向$S$外的边只有这些边。$s$指向$S$外的边全部指向$V-V'$中的正权点，它们也应当已被包含在$[S,T]$中。至此，$[S,T]$的结构就清楚了：从$s$指向$V-V'$的边，以及从$V'$指向$t$的边。发现这个割对应的点集$V'=S- \{s\}$，如果按照证明1中的方法寻找割，仍得到这个割。
一一对应关系建立完成后，试图建立最小割与最大点权的关系。对最小割$[S,T]$，记$V'=S-\{s\},\overline{V'}=T-\{t\},V'$中点权为正的点集为 $V'_+$，点权为负的点集为$V'_-$，类似地定义$\overline{V_+'},\overline{V_-'}$。那么，最小割中的边权为$w(\overline{V'_+})+w(V'_-)\left(w(V)=\sum\limits_{v\in V}{|w(v)|}\right)$。而最大点权应为$w(V'_+)-w(V'_-)$，他们的和为$w(\overline{V'_+})+w(V'_+)=w(V_+)$不变，那么取得最小割时，就会得到最大点权闭合图，问题就解决了。
由于流的上限太高，Ford-Fulkerson算法会TLE，需要用Dinic算法。
最后，在残留网络上从源点$s$出发dfs一下就知道$G'$中的点数了。挖个坑，需要证明按照这种做法得到的一定是点数最少的子图。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
struct edge {
int from, to;
long long w, f;
int rev;
edge(int i_from, int i_to, long long i_w, int i_rev) {
this->from = i_from;
this->to = i_to;
this->w = i_w;
this->rev = i_rev;
this->f = 0;
}
};
vector<edge> G[5005];
void addedge(int from, int to, long long w);
long long max_flow(int pt, long long f);
int count(int pt);
void bfs();
int level[5005];
int iter[5005];
int n, m, w[5005];
bool vis[5005];
int main()
{
long long sumw = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
if (w[i] > 0) {
addedge(0, i, w[i]);
sumw += w[i];
}
if(w[i] < 0){
addedge(i, n + 1, -w[i]);
}
}
int father, son;
for (int i = 0; i < m; i++) {
scanf("%d%d", &father, &son);
addedge(father, son, sumw + 1);
}
long long maxf = 0;
while (true) {
memset(level, -1, sizeof(level));
bfs();
if (level[n + 1] < 0) break;
memset(iter, 0, sizeof(iter));
while (true) {
long long f = max_flow(0, sumw);
if (f == 0) break;
maxf += f;
}
}
memset(vis, 0, sizeof(vis));
int cnt = count(0) - 1;
cout << cnt << " " << (sumw - maxf);
return 0;
}
void addedge(int from, int to, long long w) {
G[from].push_back(edge(from, to, w, G[to].size()));
G[to].push_back(edge(to, from, 0, G[from].size() - 1));
}
long long max_flow(int pt, long long f) {
if (pt == n + 1) {
return f;
}
long long curf = 0;
for (int &i = iter[pt]; i < G[pt].size(); i++) {
edge &v = G[pt][i];
if (level[v.to] <= level[pt] || v.w <= 0) continue;
curf = max_flow(v.to, ((f > v.w) ? v.w : f));
if (curf > 0) {
v.w -= curf;
v.f += curf;
G[v.to][v.rev].w += curf;
return curf;
}
}
return 0;
}
void bfs() {
queue<int> que;
que.push(0);
level[0] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
for (int i = 0; i < G[u].size(); i++) {
if (level[G[u][i].to] >= 0 || G[u][i].w <= 0) continue;
level[G[u][i].to] = level[u] + 1;
que.push(G[u][i].to);
}
}
}
int count(int pt) {
if(vis[pt]) return 0;
int ans = 1;
vis[pt] = true;
for(int i = 0; i < G[pt].size(); i++) {
if(vis[G[pt][i].to] || G[pt][i].w <= 0) continue;
ans += count(G[pt][i].to);
}
return ans;
}
|