网络流

网络流建模总结。

前置知识

网络流，费用流。

一，简单点的

1，二分图相关问题

设 $|X|+|Y|=n$

二分图最大匹配：$(S,x_i,1),(x_i,y_j,1),(y_j,T,1)$，设答案为 $t$。

最大独立集：$n-t$

2，多源多汇

直接新建超级源汇即可。

3，节点容量

直接拆点即可。

4，最小路径覆盖

前提：DAG。

对于每个点拆点，二分图中一条增广路径代表DAG上一条路径。

跑最大匹配，Y集合中若某个点不存在一个匹配则为一条路径的起点。

因此答案即为 $n$ - 最大匹配数。

二，不那么简单的

1，无源汇有上下界可行流

首先每条边必须得跑下界。

然后考虑一个附加流，每条的边权为上界与下界的差。

每条边最终的流量=网络流中反向边权值+下界。

对于每个点必须满足流量平衡，设 $d_u$ 为入边下界之和-出边下界之和，若 $d_u>0$ 则表明需要流多一点，$d_u<0$ 则表明可以流少一点。

因此新建超级源汇，若 $d_u<0$，则连边 $(u,t,-d_u)$，否则连边 $(s,u,d_u)$。当且仅当源点的出边满流时有解。

2，有源汇有上下界可行流

加入一条下界为 $0$，上界为 $\infty$ 的从 $t$ 到 $s$ 的边，变成上面的做法。

3，有源汇有上下界最大或最小流

先按照 1,2 的方法处理。然后删掉 1,2 中新加的边，在残量网络中跑最大流，两次答案相加即为答案。

最小流的话就把源汇反过来跑最大流就好了。

费用流同理。

4，最大权闭合子图

有向无环图，选了某个节点 $i$，则 $i$ 的后继必须选。问一种选择的方案使得选了的节点权值和最大。

假设先全部选了正的，然后最小割建图，$s$ 连节点权值为正的点，$t$ 连节点权值为负的点，减去最小割的答案即可。

三，比较难的

1，混合图的欧拉回路判定

混合图：既有有向，又有无向边的图。

欧拉回路：每条边只能且必须经过一次，最终回到起点的路径。

首先随便给无向边定向。

然后设 $d_i=出度-入度$，每给一个无向边反向都会使得某个点的 $d$ 减二，某个点的 $d$ 加二。因此若 $d_i$ 为奇数则一定无解。

若所有 $d_i$ 均为偶数，则将原图的无向边建边，容量为 $1$。然后新建源汇，容量为 $|\frac{d_i}{2}|$ 即可。

2，混合图的欧拉路径判定

若这没有 $d_i$ 为奇数的点，转成 1。

若有且只有两个 $d_i$ 为奇数的点，且一个为整，一个为负。则连一条边，变成 1。

其他情况无解。

3，最大密度子图

每个边有边权，点有点权，要去选出一个子图，使得 $\frac{\sum_{i\in E}e_i}{\sum_{i\in V} v_i}$ 最大。

显然0/1分数规划，二分答案 $mid$，有：$\frac{\sum_{i\in E}e_i}{\sum_{i\in V} v_i}\geq mid$，即 $e-mid\times v\geq 0$。

一条边选了，则它的两个点都必须选。

十分像最大权闭合子图的形式！

对于原图的每条边看做一个点，做最大权闭合子图即可判断 $mid$ 是否合法。