网络流做题记录

Xttttr / 2023-05-04 / 原文

网络流做题记录

主要用来记录除了网络流24题之外的网络流题目。

1.P4126 [AHOI2009]最小割

题意：对于每条边，求①这条边有没有可能在一种最小割中②这条边是不是一定在所有最小割中。

思路：首先看第一问。首先可以想到，如果一条边没有满流，那显然不能在最小割里。那如果满流的边一定在最小割里吗？其实不是。如果这两个点在同一个强连通分量里，那么可以让流沿着环流一遍，这样这条边就不满流了，不满足条件。于是，有可能在最小割里的充要条件是满流且两端不在同一个强连通分量里。

再看第二问，首先肯定也得满足满流的条件。其次，要满足源点可以到入点，出点可以到汇点，因为如果有一边到不了那说明在这条路径上存在一条同样可以被断掉的边，且也满足是最小割。因此可以推出，只有源点和入点在同一个强连通分量里，出点和汇点在同一个强连通分量里才能满足条件。这就是充要条件。

在实现上，先dinic再跑一编tarjan即可。

2.P3731 [HAOI2017]新型城市化

题意：\(n\)个点\(m\)条边的完全图的补图，对于每条边询问删掉这条边后原图最大团大小会不会增加。

思路：首先，因为题面中的限制，这个图可以被看成二分图，因此补图的最大团等于二分图最大独立集，证明可以考虑独立集里的点在原图中两两都有边，与一个团对应。又根据经典的结论，二分图最大独立集=点数-最小覆盖集=最大匹配，因此原题意就变成了求每条边删去后最大流是否改变。直接用上一题的做法即可。

3.P5331 [SNOI2019]通信

题意：有\(n\)个基站要通信，每个基站可以直接用\(w\)的代价与控制中心相连，也可以选择前面一个没有没连过给基站，代价是\(|a_i-a_j|\)，求最小总代价。

思路：首先有一个很明显的拆点后\(O(n^2)\)建边后跑费用流的做法，但\(n^2\)条边肯定会T，于是考虑优化建边。例如，可以考虑把\(a_i\)排序后依次相连，用累加差来表示代价，但这样不好确定每个点拆出来的点中哪个与这些点相连，于是考虑分治。对于区间\((l,r)\)，\((l,mid)\)的点拆除来的出点与表示代价的点相连，\((mid+1,r)\)的点拆出来的入点与表示代价的点相连，然后跑费用流就可以了。

4.P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

题意：~~（这题目怎么这么长）~~ 有\(n\)天，每天最多拍\(D_i\)张照片，有\(C_i\)个取材对象，每个取材对象\(T_{i,j}\)需要拍\([L_{i,j},R_{i,j}]\)的照片，同时\(m\)个少女中每个少女的照片数量不得少于\(G_i\)。

思路：既然是模板那就按模板来写。

无源汇上下界可行流

这是上下界网络流中最简单的一种，给定一个没有源点和汇点、每条边的流量有上下界的流量网络，问是否存在一种可行流使得流量平衡，即每个点的流入量等于流出量。我们的做法是，把它拆成两个网络，一个每条边的容量是下界（下界网络），另一个每条边的容量是上下界之差（差网络），这时条件就是两个网络的流量之和是一种科可行流。首先，下界网络肯定得满流，但是这样不一定是可行流，于是可以通过差网络把这些不平衡的地方补上。具体地，我们在差网络中新设一个源点和汇点，如果一个点在下界网络里流入量比流出两多\(\Delta\)，那么就从在差网络中由源点向这个点连一条容量为\(\Delta\)的附加边，如果流出量比流入量多\(\Delta\)，就由这个点向汇点连容量为\(\Delta\)的附加边。这时再跑差网络的最大流，如果满足每条附加边都满流，那么这就是一个可行流；反之，就不存在可行流。

在代码实现的时候，不用把下界网络建出来，直接在差网络上跑就行。