「网络流学习笔记Part II」总之XJB写点啥（

Part I 大概是这篇。

去郑州的时候讲的网络流部分。

什么你说游记？咕咕咕。

一种似乎没有名字的二元组模型

简化版

你有两台机器和 $n$ 个任务。用第一台机器完成第 $i$ 个任务需要付出 $a_{i}$ 的代价，用第二台完成需要 $b_{i}$ 的代价。你有 $m$ 个三元组（虽然说不是标题说的二元组不过不要在意这些细节），每一个三元组形如 $(x,y,c)$，意思是如果 $x$ 和 $y$ 两个任务在不同的机器上完成需要额外付出 $c$ 的代价。你需要完成这 $n$ 个任务，并最小化代价和。

我们都知道最小割 = 最大流。因此在一些题目中，如果无法将问题抽象成最大流问题，我们可以试着抽象成最小割问题。

对于任务 $i$，连边 $(S,i,a_{i}),(i,T,b_{i})$。对于一个三元组 $(x,y,c)$，连边 $(x,y,c),(y,x,c)$。

割断 $(S,i,a_{i})$ 意味着任务 $i$ 在第一台机器上完成，割断 $(i,T,b_{i})$ 意味着任务 $i$ 在第二台机器上完成。

首先很明显的是，同时割断 $(S,i,a_{i})$ 和 $(i,T,b_{i})$ 一定不是最优的决策。因此一个任务只会在一台机器上被完成。

对于一个三元组 $(x,y,c)$，如果我们同时割断 $(S,x,a_{x})$ 和 $(S,y,a_{y})$，$S$ 与 $T$ 直接就断开了，这样我们的代价是 $a_{x}+a_{y}$。同时割断 $(x,T,b_{x})$ 和 $(y,T,b_{y})$ 也是类似的。

如果说我们同时割断 $(S,x,a_{x})$ 和 $(y,T,b_{y})$，图上仍存在 $\{(S,y,a_{y}),(y,x,c),(x,T,b_{x})\}$ 这样一条路径，我们还需要割断 $(y,x,c)$，这样我们的代价是 $a_{x}+b_{y}+c$。同时割断 $(x,T,b_{x})$ 和 $(S,y,a_{y})$ 也是类似的。

一般化

你有两台机器和 $n$ 个任务。用第一台机器完成第 $i$ 个任务需要付出 $a_{i}$ 的代价，用第二台完成需要 $b_{i}$ 的代价。你有 $m$ 个六元组，每一个六元组形如 $(x,y,c_{1},c_{2},c_{3},c_{4})$，意思是你需要为 $x$ 和 $y$ 这两个任务付出一些额外代价：

• 如果任务 $x$ 在第一台机器上完成，任务 $y$ 在第一台机器上完成，这个额外代价是 $c_{1}$。
• 如果任务 $x$ 在第二台机器上完成，任务 $y$ 在第二台机器上完成，这个额外代价是 $c_{2}$。
• 如果任务 $x$ 在第一台机器上完成，任务 $y$ 在第二台机器上完成，这个额外代价是 $c_{3}$。
• 如果任务 $x$ 在第二台机器上完成，任务 $y$ 在第一台机器上完成，这个额外代价是 $c_{4}$。

你需要完成这 $n$ 个任务，并最小化代价和。

首先仍然是连边 $(S,i,a_{i}),(i,T,b_{i})$。对于每一个六元组，连边 $(S,x,A),(S,y,B),(x,T,C),(y,T,D),(x,y,E),(y,x,F)$。我们发现

• 如果任务 $x$ 在第一台机器上完成，任务 $y$ 在第一台机器上完成，我们需要割断 $(S,x,A),(S,y,B)$，付出 $A+B$ 的代价。
• 如果任务 $x$ 在第二台机器上完成，任务 $y$ 在第二台机器上完成，我们需要割断 $(x,T,C),(y,T,D)$，付出 $C+D$ 的代价。
• 如果任务 $x$ 在第一台机器上完成，任务 $y$ 在第二台机器上完成，我们需要割断 $(S,x,A),(y,T,D),(y,x,F)$，付出 $A+D+F$ 的代价。
• 如果任务 $x$ 在第二台机器上完成，任务 $y$ 在第一台机器上完成，我们需要割断 $(S,y,B),(x,T,C),(x,y,E)$，付出 $B+C+E$ 的代价。

因此我们列出如下的方程组

$$\begin{cases} &A+B=c_{1}&(1)\\ &C+D=c_{2}&(2)\\ &A+D+F=c_{3}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;&(3)\\ &B+C+E=c_{4}&(4) \end{cases}$$

因为我们要将问题转化成最大流问题，首先想到，我们要有 $A,B,C,D,E,F\geqslant 0$。注意到，$(S,x,A)$ 和 $(x,T,C)$ 中有且仅有一条边会出现在最小割集中，因此我们可以将 $A$ 和 $C$ 同时加上一个数，求出最小割后在答案中减去。$B$ 和 $D$ 也可以类似处理。

需要注意的是，$E$ 和 $F$ 不能被这样处理，因为我们不能确定它们在答案中产生了几次贡献。

$(3)+(4)-(1)-(2)$，我们得到

$$E+F=c_{3}+c_{4}-c_{1}-c_{2}$$

定义 $K=c_{3}+c_{4}-c_{1}-c_{2}$，当 $K\geqslant 0$ 时它有意义，我们直接令 $E=F=\cfrac{K}{2}$ 即可。

剩下的四个量随便给几个值，好算就行。

其实就算 $K\lt 0$ 有时也是可以做的，但是我太菜了不会（

因为太菜了所以没有图（

例题

「国家集训队」happiness

题目要求最大化总收益，我们可以先将所有数取相反数，然后最小化总代价。

令位置 $i$ 选文的单独收益是 $a_{i}$，选理的单独收益是 $b_{i}$，连边 $(S,i,-a_{i}),(i,T,-b_{i})$。

考虑一对相邻的位置，他们都选文的额外收益是 $v_{1}$，都选理的额外收益是 $v_{2}$，列出方程组

$$\begin{cases} &A+B=-v_{1}\\ &C+D=-v_{2}\\ &A+D+E=0\\ &B+C+E=0 \end{cases} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \begin{cases} &A=-\cfrac{v_{1}}{2}\\ &B=-\cfrac{v_{1}}{2}\\ &C=-\cfrac{v_{2}}{2}\\ &D=-\cfrac{v_{2}}{2}\\ &E=\cfrac{v_{1}+v_{2}}{2} \end{cases}$$

为了避免浮点数，我们把上面所有边的容量乘以 $2$，包括 $(S,i,-a_{i}),(i,T,-b_{i})$，最后再除回来。

然后，为了避免负数，我们将 $A,B,C,D$ 加上 $v_{1}+v_{2}$，把边 $(S,i,-2a_{i}),(i,T,-2b_{i})$ 的容量加上 $2a_{i}+2b_{i}$，最后再减回来。

总结一下就是，对于一个位置 $i$，连边 $(S,i,2b_{i}),(i,T,2a_{i})$。对于一对相邻位置 $x,y$，连边 $(S,x,v_{2}),(S,y,v_{2}),(x,T,v_{1}),(y,T,v_{1}),(x,y,v_{1}+v_{2}),(y,x,v_{1}+v_{2})$。

$$\text{Ans}=\sum(a_{i}+b_{i})+\sum(v_{1}+v_{2})-\cfrac{\text{MinCut}(S,T)}{2}$$

但是我的代码 不知道为什么写炸了（

反正这个式子应该是没问题的（

那么告辞吧（

闭合子图

定义

对于一个有向图 $G$，它的一个闭合子图指的是一个顶点集合 $V$，满足 $V\subset G$，且

$$\forall u\in V\wedge(u,v)\in G,v\in V$$

其中 $|V|$ 最大的 $V$ 被称为 $G$ 的最大闭合子图。

如果 $G$ 中的点有点权，$\sum_{u\in V}w(u)$ 最大的 $V$ 被称为 $G$ 的最大权闭合子图。

解法

首先，我们还是需要将所有点权取相反数，转为求最小权闭合子图。

对于 $G$ 中的一个点 $x$，割断与 $S$ 之间的边表示 $x\notin V$，割断与 $T$ 之间的边表示 $x\in V$。对于 $G$ 中的一条边 $(x,y)$，如果 $x\in V$，那么一定有 $y\in V$。我们可以认为，如果令 $x\in V$，$y\notin V$，需要付出 $+\infty$ 的代价。由此列出方程组

$$\begin{cases} &A+B=0\\ &C+D=-w(x)-w(y)\\ &A+D+F=-w(x)\\ &B+C+E=-w(y)+\infty \end{cases} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \begin{cases} &A=0\\ &B=0\\ &C=-w(x)\\ &D=-w(y)\\ &E=+\infty\\ &F=0 \end{cases}$$

于是，去掉所有容量为 $0$ 的边，我们得到 $(x,T,-w(x)),(y,T,-w(y)),(x,y,+\infty)$ 这三条边。如果 $w(x)\geqslant 0$，我们需要把边 $(S,x,0),(x,T,-w(x))$ 的容量都加上 $w(x)$，相当于是把 $(x,T,-w(x))$ 换成了 $(S,x,w(x))$。

总结一下就是，对于原图中的一个正权点 $x$，连边 $(S,x,w(x))$，对于原图中的一个负权点 $x$，连边 $(x,T,-w(x))$。对于原图中的一条边 $(x,y)$，连边 $(x,y,+\infty)$。

$$\text{Ans}=\sum_{w(x)\geqslant 0}w(x)-\text{MinCut}(S,T)$$