挑战程序竞赛系列（25）：3.5最大权闭合图
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434646
挑战程序竞赛系列（25）：3.5最大权闭合图
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 2987: Firing
思路可以参考博文：http://www.hankcs.com/program/algorithm/poj-2987-firing.html
这种最大权闭合图转最大流的思路着实巧妙，具体步骤如下：
- 先构造网络流N，添加源点s，从s到正权值点做一条边，容量为点的权值。
- 添加汇点t，从负权值点到t做一条边，容量为点的权值的绝对值。
- 原来的边的容量统统设为无穷大。比如：
- 求解最小割，最大权=正权值之和-最小割权值
- 残余网络中的点的个数即为裁员个数。
当然证明可以参考：《算法合集之《最小割模型在信息学竞赛中的应用》.pdf》
用人类的语言描述下为什么是正确的吧，首先需要明确几个点，假设取1，则连带的有1，2，4，5都会被牵扯进来，所以{1,2,4,5}就形成了一个小群体，称为最大权闭合图，weight{1,2,4,5}就是该集合的权值，题目要求该值最大，比较容易理解。那么选择结点2会发生什么情况？最大权闭合图变为了{2,5}，所以选取不同的结点，所导致的闭合图也会不同，因此有了求max weight的这道题。
思路：最大权闭合图等价于简单割（当然是转换成图N的情况下），或者可以这么理解，每个从源点s出发的简单割与最大权闭合图一一对应。
问题来了，简单割是什么？和之前最大流中的割集有什么关系？应该说简单割是割集的一种特殊情况，即此割集的流量不为正无穷的情况称为简单割。
你可以把集合{1,2,4,5,s}看成S，那么剩余的结点为T，而该割集的CS,T必然是一个非无穷的正值。
证明：想象一下，由最大权闭合图组成的点集U{s}，必然不会存在从该点集出来的边指向其他顶点，所以S到T的容量不可能包含正无穷。（证毕）
那么该问题就变成了求最小简单割（即最大流的最小割算法），那为啥上述公式就是答案了呢？最大权=正权值之和-最小割权值？
巧妙在于从s出发的边都是连接正权值的顶点，而汇点则都是负权值顶点指向t，所以当我们用简单割包含闭合图时，必然S到T的流量一定由负权值组成，那么某些正权值怎么办呢？分两种情况：
- 正权值的顶点不在简单割集内，这种说明该顶点在可选和不可选中选择了不可选，所以s到该顶点必然有个正的分量，包含在简单割中。
- 正权值的顶点在简单割集内，这种说明该顶点在可选和不可选中选择了可选，所以简单割中不存在该容量。
那么最大权 = 所有正权值 - 简单割，就变成了选择顶点的正值之和 - 负权值的容量之和。（证毕）
这样就把每个顶点可选和不选的情况，统一到求解最小割集，即求解最大流，高明。
代码如下：（TLE）
static class Edge{
int from;
int to;
long cap;
int rev;
public Edge(int from, int to, long cap, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
static long INF = 1 << 62;
static List<Edge>[] g;
static int V;
static int S;
static int T;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
V = N + 2;
S = 0;
T = N + 1;
count = 0;
visited = new boolean[V];
level = new int[V];
g = new ArrayList[V];
for (int i = 0; i < V; ++i){
g[i] = new ArrayList<Edge>();
}
long pos = 0;
for (int i = 0; i < N; ++i){
long cap = in.nextInt();
if (cap > 0){
addEdge(S, i + 1, cap);
pos += cap;
}
else{
addEdge(i + 1, T, -cap);
}
}
for (int i = 0; i < M; ++i){
int from = in.nextInt();
int to = in.nextInt();
addEdge(from, to, INF);
}
long min = dinic();
solve(S);
System.out.println((--count) + " " + (pos - min));
}
public static void addEdge(int from, int to, long cap){
g[from].add(new Edge(from, to, cap, g[to].size()));
g[to].add(new Edge(to, from, 0, g[from].size() - 1));
}
static int[] level;
public static void bfs(int s){
for (int i = 0; i < V; ++i) level[i] = -1;
level[s] = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(s);
while (!queue.isEmpty()){
int v = queue.poll();
for (Edge e : g[v]){
int to = e.to;
if (level[to] < 0 && e.cap > 0){
level[to] = level[v] + 1;
queue.offer(to);
}
}
}
}
public static long dfs(int s, int t, long F, boolean[] visited){
if (s == t) return F;
visited[s] = true;
for (Edge e : g[s]){
int from = e.from;
int to = e.to;
if (!visited[to] && level[from] + 1 == level[to] && e.cap > 0){
long d = dfs(to, t, Math.min(F, e.cap), visited);
if (d > 0){
e.cap -= d;
g[to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}
public static long dinic(){
long flow = 0;
for (;;){
bfs(S);
if (level[T] < 0) break;
long f = 0;
while ((f = dfs(S, T, INF + 16, new boolean[V])) > 0) flow += f;
}
return flow;
}
static int count;
static boolean[] visited;
public static void solve(int s){
count ++;
visited[s] = true;
for (Edge e : g[s]){
int to = e.to;
if (e.cap > 0 && !visited[to]){
solve(to);
}
}
}嘿，JAVA代码怎么又TLE了，心累，改成C++能AC。c++代码参考博文：http://www.hankcs.com/program/algorithm/poj-2987-firing.html
POJ 2914: Minimum Cut
求无向图的最小割集，起初的想法是把无向图构造成有向图，接着遍历所有可能的源点和汇点，但发现这种时间复杂度相当高，于是得另辟蹊径了。
其实它是著名的stoer_wagner算法。。。好吧，又超出自己的能力范围学习起来痛苦万分。可以说它是一种符合某种情形下的遍历，又或者有点像松弛法，因为它的核心思想是，不断改进解，直到解不能再改变，或者说它的所有情况都被遍历完了，自然最后留下的便是最小割集。
来说说它的思路吧，这比较有趣，既然是不断改善解，那么我们自然就能想到遍历所有源点和汇点，找寻任意一对源点和汇点的最小割集，那它是全局的最小割集么？
不一定，假设全局的最小割集已知，那么上述任意的源点s和汇点t会出现两种情况：
- 源点在最小割集的S部分，汇点在最小割集的T部分，此时你所遍历的源点和汇点的最小割集就是全局的最小割集，那么恭喜你，你很幸运一下子就找到了正确解。但如果不是呢？
- 另外一种情况是说源点和汇点都在全局最小割集的S部分或者T部分，那么显然你所找的关于s和t的最小割集一定不是最小的，但你会更新minCut，没关系，既然在全局最小割集的某一半部分，那么s和t合并之后再去求解最小割集是不会影响全局最小割集的。
第二点可以理解成，哪怕你找到了源点s和汇点t正好是全局的最小割集，我们依旧假设它们位于全局最小割集的某一部分S或者T，这样程序会继续执行，保证全局是最优的（自然某个时刻你找到的s和t是全局最小割集），那么是什么降低了时间复杂度？
合并，每次合并，意味着找寻最小割集的顶点都会少一个，而且我们不需要遍历所有可能的源点和汇点，而是从中找任意一个源点和汇点即可。
所以现在的问题是：给定一个无向图，如何找到一个源点s和一个汇点t的最小割集呢？
stoer_wagner算法告诉我们：
- 设最小割cut=INF, 任选一个点s到集合A中, 定义W(A, p)为A中的所有点到A外一点p的权总和.
- 对刚才选定的s, 更新W(A,p)(该值递增).
- 选出A外一点p, 且W(A,p)最大的作为新的s, 若A!=G(V), 则继续2.
- 把最后进入A的两点记为s和t, 用W(A,t)更新cut.
- 新建顶点u, 边权w(u, v)=w(s, v)+w(t, v), 删除顶点s和t, 以及与它们相连的边.
- 若|V|!=1则继续1.
证明：采用反证法，假设存在存在两个候选的结点t1, t2，如果选择较小的W(A, t1)进入s，那么必然A与t2产生割集，而它们的边权之和等于W(A, t2) + W(t1, t2)，不管t1和t2之间是否有边相连，选择t1产生的割集一定比选择t2产生的割集大，这就与假设矛盾，意味着必须选择较大的W(A, p)进入集合A。
代码如下：
static int INF = 0x3f3f3f3f;
static int[][] g;
static int[] v;
static int[] w;
static int N;
static boolean[] visited;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
String[] nums = in.nextLine().trim().split(" ");
N = Integer.parseInt(nums[0]);
int M = Integer.parseInt(nums[1]);
g = new int[N][N];
v = new int[N];
for (int i = 0; i < M; ++i){
nums = in.nextLine().trim().split(" ");
int from = Integer.parseInt(nums[0]);
int to = Integer.parseInt(nums[1]);
int cap = Integer.parseInt(nums[2]);
g[from][to] += cap;
g[to][from] += cap;
}
System.out.println(stoerWagner(N));
}
in.close();
}
public static int stoerWagner(int n){
int minCut = INF;
for (int i = 0; i < n; ++i){
v[i] = i;
}
while (n > 1){
int pre = 0;
w = new int[N];
visited = new boolean[N];
for (int i = 1; i < n; ++i){
int k = -1;
for (int j = 1; j < n; ++j){ //求每次加入集合A之后的最大权值
if (!visited[v[j]]){
w[v[j]] += g[v[pre]][v[j]];
if (k == -1 || w[v[k]] < w[v[j]]){
k = j;
}
}
}
visited[v[k]] = true;
if (i == n - 1){
int s = v[pre], t = v[k];
minCut = Math.min(minCut, w[v[k]]); //更新最小割集
for (int j = 0; j < n; ++j){ //结点s和结点t合并
g[s][v[j]] += g[v[j]][t];
g[v[j]][s] += g[v[j]][t];
}
v[k] = v[--n]; //删除结点k
}
pre = k;
}
}
return minCut;
}差一点又超时了，合并的代码比较新颖，学习了。
POJ 3155: Hard Life
翻译参考：http://www.hankcs.com/program/algorithm/poj-3155-hard-life.html
心机婊：公司内部共 n 个员工，员工之间可能两两合不来。若员工u 和员工 v 有矛盾，用边(u, v)表示，共 m 个矛盾。突然大股东送来一个富二代，威胁到你的CEO宝座。你想分配给富二代一个垃圾团队，使得团队成员间的不团结率最高。不团结率定义为团队人员间的矛盾总数与被裁人员数的比值（不团结率 = 团队人员之间的矛盾总数 / 团队人员数）。
好吧，此题是经典的求最大密度子图，所需要的知识点较多，覆盖了分数规划，二分法，以及最大流，最小割等知识点。
具体可以参考算法合集系列《算法合集之《最小割模型在信息学竞赛中的应用》.pdf》
此处说说一些思路，还是比较容易理解的，首先对该问题进行形式化，于是有了：
Maximize D=f(x)=∑e∈E1⋅xe∑v∈Vxv
Maximize \space D = f(x) = \frac{\sum_{e \in E} 1 \cdot x_e}{\sum_{v \in V} x_v}
于是就联想到了分数规划。。。接着就可以用二分了。。。好吧，说实话，我不知道怎么就能联想到分数规划了， 不过之前在leetcode刷题时，看到一些统一的模式，总结一下。它们都是求解极值问题，在所有符合子图性质情况下，求所有子图G′G'下的最大密度。所以，我们可以假定一个值g，有：
D=f(x)=∑e∈E1⋅xe∑v∈Vxv=g
D = f(x) = \frac{\sum_{e \in E} 1 \cdot x_e}{\sum_{v \in V} x_v} = g
于是式子就变成了：
h(g)=∑1⋅xe−∑g⋅xv
h(g) = \sum 1 \cdot x_e - \sum g \cdot x_v
典型的分数规划模型，当h(g) < 0时，说明D < g，此时g太大，应该把g调小，而当h(g) > 0 时，说明D > g，此时需要调小g，直到g = d时，完成迭代。
说实在的，我们无非直接求出∑1⋅xe−∑g⋅xv=0\sum 1 \cdot x_e - \sum g \cdot x_v = 0的解，遇到的困难是我们无法得到最大密度子图G′G'，所以我们只能利用二分，假定存在一个解，这样就能构造一个变形的图。
所以该问题就变成了max{h(g)}，需要注意的是，为什么这里还存在一个max呢？因为构造h(g)的子图G′G'可以有多组，为了让所有的子图都小于等于D，必须让h(g)最大的满足h(g) = 0，此时的g才符合所有子图的最大的那个。
于是问题进一步转换成：
Maximize |E′|−g|V′|
Maximize \space \vert E'\vert - g \vert V'\vert
此时《算法合集》中，利用了边的出度来计算V′V'下的边数，高明。但乍看一下，公式好像有点问题，个人觉得是：
minimize g⋅|V′|−|E′|=∑v∈V′(2⋅g−dv)+cV′,V′^
minimize \space g \cdot \vert V'\vert - \vert E'\vert = \sum_{v \in V'} (2 \cdot g - d_v) + cV', \hat {V'}
接着开始构造图G的转换图N，构造规则比较简单：
- 新建源点s，和汇点t
- s连接的顶点权值为u（图G的边数即可）
- 所有顶点连接汇点的权值为u + 2g - dv
- 其他顶点之间存在边则连接，权值为1
此时图N的最小割集算法就是上述的min目标函数，证明比较好理解，把图N分割成S和T，此时S到T的割集存在三部分，第一部分是原先的边权值为1的那些顶点，实际上求的是cV′,V′^cV', \hat {V'}，第二部分是源点到所有在T中的顶点权值之和，为U|V′^|U\vert \hat{V'}\vert，第三部分是从S出发的顶点到汇点的权值之和，为U|V′|U\vert V'\vert.
所以整体代码如下：
class Pair{
int from;
int to;
public Pair(int from, int to){
this.from = from;
this.to = to;
}
}
double[][] graph;
Pair[] p;
int[] dv;
int N;
static final double esp = 1e-8;
void solve() {
N = ni();
int M = ni();
if (M == 0){
out.println("1");
out.println("1");
}
else{
dv = new int[N + 2];
graph = new double[N + 2][N + 2];
p = new Pair[M];
for (int i = 0; i < M; ++i){
int from = ni();
int to = ni();
dv[from] ++;
dv[to] ++;
p[i] = new Pair(from, to);
}
int s = 0, t = N + 1;
double lo = 1.0 / N;
double hi = M / 1.0;
double precision = 1.0 / N / N;
double hg = 0.0;
while (hi - lo >= precision){
double mid = (hi + lo) / 2.0;
constructGraph(mid, N, M);
hg = (N * M - dinic(0, N + 1)) / 2.0;
if (hg > esp) lo = mid;
else hi = mid;
}
constructGraph(lo, N, M);
dinic(s, t);
sum = 0;
boolean[] marked = new boolean[N + 2];
dfsTravel(s, marked);
out.println(sum - 1);
for (int i = 1; i <= N; ++i){
if (marked[i]){
out.println(i);
}
}
}
}
int sum;
public void dfsTravel(int v, boolean[] visited){
++sum;
visited[v] = true;
for (int j = 0; j < N + 2; ++j){
double cap = graph[v][j];
if (cap > 0.0 && !visited[j]){
dfsTravel(j, visited);
}
}
}
int[] level;
public void bfs(int s){
level = new int[N + 2];
Arrays.fill(level, -1);
level[s] = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(s);
while (!queue.isEmpty()){
int v = queue.poll();
for (int to = 0; to < N + 2; ++to){
double e = graph[v][to];
if (level[to] < 0 && e > 0){
level[to] = level[v] + 1;
queue.offer(to);
}
}
}
}
public double dfs(int s, int t, double f, boolean[] visited){
if (s == t) return f;
visited[s] = true;
for (int to = 0; to < N + 2; ++to){
double cap = graph[s][to];
if (!visited[to] && level[s] + 1 == level[to] && cap > 0){
double d = dfs(to, t, Math.min(f, cap), visited);
if (d > esp){
graph[s][to] -= d;
graph[to][s] += d;
return d;
}
}
}
return 0.0;
}
static final double INF = Double.MAX_VALUE;
public double dinic(int s, int t){
double flow = 0;
for (;;){
bfs(s);
if (level[t] < 0) break;
double f = 0;
while ((f = dfs(s, t, INF, new boolean[N + 2])) > 0) flow += f;
}
return flow;
}
public void constructGraph(double g, int N, int M){
graph = new double[N + 2][N + 2];
for (int i = 1; i <= N; ++i){ //s -> v
addEdge(0, i, M);
addEdge(i, N + 1, M + 2 * g - dv[i]);
}
for (Pair pair : p){
int from = pair.from;
int to = pair.to;
addEdge(from, to, 1);
addEdge(to, from, 1);
}
}
public void addEdge(int from, int to, double cap){
graph[from][to] += cap;
}不容易啊，居然过了。