【施工中】
网络流24题题解及常见套路总结
本文已重置,请访问 https://www.cnblogs.com/birchtree/p/12912607.html 查看最新版本
目录
点击链接进入各题题解，常见套路总结见下方
| 问题名称 | 问题模型 | 转化模型 |
|---|---|---|
| 飞行员配对方案问题 | 二分图最大匹配 | 最大流 |
| 最小路径覆盖问题 | 有向无环图最小路径覆盖 | 最大流 |
| 魔术球问题 | 有向无环图最小路径覆盖 | 最大流 |
| 圆桌问题 | 二分图多重匹配 | 最大流 |
| 最长递增子序列问题 | 最多不相交路径 | 最大流 |
| 试题库问题 | 二分图多重匹配 | 最大流 |
| 家园 | 分层图最大流 | 最大流 |
| 太空飞行计划问题 | 最大权闭合图 | 最小割 |
| 方格取数问题 | 二分图点权最大独立集 | 最小割 |
| 骑士共存问题 | 二分图最大独立集 | 最小割 |
前置知识清单
掌握：
网络流的性质
最大流的EK与Dinic算法，费用流的EK算法
Dijkstra,SPFA最短路算法
了解定义：
二分图相关定义
最小割定义，最小割最大流定理
最大流
二分图最大匹配与多重匹配
定义：
二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不相交，则称M是一个匹配。二分图最大匹配则是使边数最多的匹配
二分图多重匹配：每个节点不一定只与一条边相连，而是限制了最多连的边数（当限制为1时退化为二分图最大匹配
建图方法
对于一张二分图，我们可以从源点S向左部节点连有向边，右部节点向汇点T连有向边，原二分图每条边看作从左到右的有向边
假如把所有边的流量设为1，则二分图的最大匹配数就等于S到T最大流，所有有流经过的边为匹配边(记住这一点，因为不少题目要求输出方案)
如果要求二分图多重匹配，则只需把S向左部点的有向边容量设为左部点匹配数量上限，右部点同理
二分图一般匹配：飞行员配对方案问题
最小路径覆盖
最小路径覆盖定义：在一个有向无环图中，找出最少的路径，使得这些路径经过了所有的点。
最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖，区别是这些路径是否可以相交
把原图的每个点u拆成两个点u1,u2，如果有一条有向边a->b,则连边a2->b1，容易发现这是一个二分图
最小路径覆盖=原图节点数-新图最大匹配数
证明：
一开始每个点都是一条路径，每次找一条匹配边，代表合并两条路径
由于路径不相交（即每个点的入度和出度至少有一个为1），所以二分图上的边也不相交（如果相交则说明某个点的入度或出度大于1），这正好是匹配的定义
每条匹配边代表答案-1，所以最小路径覆盖=原图节点数-新图最大匹配数
最多不相交路径
这种问题变化比较多，但都能表示成以下形式：已知一些路径，每个节点只能属于一条路径，求能选择多少条路径使它们不相交主要的方法是拆点，将一个点拆成两个，然后连边，容量表示该点最多经过次数
最小割
最大权闭合子图
定义：有一个有向图，每一个点都有一个权值，选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。
如图，括号外的为点的编号，括号内的为点的权值,则闭合子图有{1,2,3,4} {2,4} {3} {4}{空},最大的闭合子图是{1,2,3,4},权值和为9
建图方法：
从源点s向每个正权点连一条容量为权值的边，每个负权点向汇点t连一条容量为权值的绝对值的边，有向图原来的边容量全部为无限大。
最大权闭合子图=所有正权点之和-最小割
证明：
关键性质：如果s与i有边，表示i在子图中。如果i与t有边，表示i不在于子图中。.即：割掉s与i表示不选i,割掉i与t表示选i**
引理1:原图之间的边一定不会被割掉
边权为无穷大，当然不会被选进最小割
引理2：只有s到t不联通时，才得到最大权闭合子图
反证法：若s到t连通，则一定存在节点i,j使s到i有边，i到j有边（引理1），j到t有边
而根据性质1:i在子图中，j不在子图中，这与最大权闭合子图的定义矛盾，证毕
由引理2可得，图的一个割就是一个闭合子图
由于一个割的边权和=不选的正权点+选的负权点绝对值=不选的正权点-选的负权点
闭合子图=选的正权点+选的负权点
=所有正权和-不选的正权点+选的负权点
=所有正权和-(不选的正权点-选的负权点)
=所有正权和-割的边权和
显然割的边权和最小的时候得到最大权闭合子图，证毕
应用:
当问题中出现一种冲突时，就可以采用最大权闭合子图。具体来说，对于一个事件，只能得到a收益和b收益之中的一种。我们就把a收益作为正权点，b收益作为负权点，跑最大权闭合子图
二分图独立集
其实二分图独立集是特殊的一种最大权闭合子图
我们根据上文“收益”的思想，把选某个点的收益看为1，左部节点为正权点，右部节点为负权点。按照最大权闭合子图的方式建图，答案为正权和-最小割=n-最小割=n-最大流。我们发现把最大权闭合子图中INF的边换成1也不影响答案，因为图中其他边的容量都为1
这样图就变成了二分图匹配中的图，最大流=二分图最大匹配。所以二分图最大独立集=n-二分图最大匹配
最小割例题：
分层图最短路与最大流
先放一道纯最短路的题(不知道该放在哪里)：
分层图最短路
分层图是一种状态是多维的的图
它是由一个图不断复制形成的
这就是一个分层图，它由图{1,2,3}复制了三次形成
通常情况下须要用到分层图的题目都有一些操作，操作可能会改变边权或者连边方式，我们的解决方法就是把原图复制，然后修改，并在不同层次图的点之间连起新的边。 每一层图都是由原图复制来的。因此这些不同层次的图的结构和性质类似
在实现上，邻接表里不一定要存储所有的边，可以只存储原图，但是一些数组用二维数组来表示，如(dist[i][u])表示第i层的u号节点
这是分层图上的spfa算法的(伪)代码
struct node{
int floor;//层数
int num;//节点编号
}
queue<node>q;
int dist[maxl][maxn];//距离
int inq[maxl][maxn];//是否在队列种
int spfa(node s,node t){
q.push(s);
memset(dist,0x3f,sizeof(dist));
dist[s.floor][s.num]=0;
while(!q.empty()){
node x=q.front();
q.pop();
inq[x.floor][x.num]=0;
for(y : 从x可以到达的节点){
if(dist[y.floor][y.num]>dist[y.floor][y.num]+w){//w为转移代价
dist[y.floor][y.num]=dist[y.floor][y.num]+w;
if(!inq[y.floor][y.num]){
inq[y.floor][y.num]=1;
q.push(y);
}
}
}
}
return dist[t.floor][t.num];
}
很多时候分层图最短路也可以通过BFS解决，但SPFA会稍快一些