网络流与线性规划 24 题

· · 个人记录

因为感觉做网络流让人神清气爽——毕竟网络流就是这样的，写网络流的人只需要考虑建图就好了，而用其它写法的人要考虑的就多了——所以决定写一写全部 24 题，稍微糊一些做法在这篇文章里。

不一定由易到难

圆桌问题

建图比较的版。考虑每个单位和餐桌当成一个点，从源点到汇点流过 1 的流量当成配对一个人，那么我们就建一个超级源向所有单位连一条流量为单位人数的边，每个单位向每个餐桌连一条流量为 1 的边，每一个餐桌向超级汇连一条流量为餐桌最大人数的边，跑最大流即可。如果最大流不等于人数和，那就无解，否则看单位与餐桌之间的边有没有流干净，流干净了就说明这个单位有一个人去了这个餐桌。

飞行员配对方案问题

这不就是二分图最大匹配吗？为什么要评蓝？

那就稍微说一下网络流最大流做二分图匹配：

建一个超级源向左边的每一个点连一条流量为 1 的边，右边的每一个点向超级汇连一条流量为 1 的边（一个点只能在一条边上），再给原来的每条边附一个流量为 1（一条边只能算一次），跑做大流即可。

构造方案的方法和圆桌问题类似。

骑士共存问题

一个骑士可以存在当且仅当他每一个能攻击到的位置都没有其它骑士。对于这种满足所有条件，就能产生相应贡献的题目，尝试转化为最小割模型。将答案设为所有无障碍格子总数，再减去最少的不合法骑士，就是答案。对于求解“最少不合法骑士”，使用最小割（最大流）解决。

考虑给网格黑白染色，(1,1) 为黑，与黑色格子相邻的格子为白，与白色格子相邻的格子为黑。容易发现，骑士能攻击到的地方的颜色一定和自身所在颜色不同。

考虑将超级源连向每个无障碍黑点，每个无障碍白点连向超级汇，边权都为 1（一个点只能放一个骑士）。接下来对于每个无障碍黑点，向所有它能到达的白点连一条边权无穷大的边，跑最小割即可。

考虑一下这样建边的原因。因为如果一个白点连接的所有黑点有一个与汇点之间的边没有被割掉，那白点与源点相连的边也必须割掉，否则源与汇之间就联通了。把割边理解成废除，也就是一个点所能到达的所有点只要有一个没有被废除，那这个点就不能存在，必须废除，满足题目要求。

分配问题

第一道最小费用最大流，纪念一下。

超级源向每个点连一条流量为 1，费用为 0 的边，每个店向超级汇连一条流量为 1，费用为 0 的边，点 i 向点 n+j（第 j 个工作对应点的编号为 n+j）连一条流量为 1（只要大于等于 1 都行），费用为 c_{i,n+j} 的边，跑两遍（边权取反再跑第二遍）最小费用最大流即可。

稍微解释一下。流量为 1 保证一个工人只能做一件工作以及一件工作只能被一个工人做。最大流的前提保证每个工人都有工作做。然后就是求解最小费用就行了。

运输问题

和分配问题几乎一致，也是最小费用最大流。只不过超级源和点 i 的流量改为 a_i，点 n+i 和超级汇的流量改为 b_i。然后 i 与 n+j 之间的流量确定为无穷大（大于等于 \min(\max a_i,\max b_i) 都行）。原理上同。

孤岛营救问题

第一道完全不用网络流的 24 题之一。毕竟是想要练习网络流，故予奋力想网络流之法，未果，遂放弃。如果有人知道网络流做法的可以私信我补上。

因为钥匙种类很少，所以可以状压+bfs，思路过于简单，不赘述了。

在努力做（蒻），持续更新！