网络流做题记录

网络流做题记录

主要用来记录除了网络流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\)的附加边。这时再跑差网络的最大流，如果满足每条附加边都满流，那么这就是一个可行流；反之，就不存在可行流。

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

有源汇上下界可行流

虽然是有源汇，但其实很简单。我们考虑，如果汇点向源点连容量为\(inf\)的边，再跑无源汇上下界可行流，就等价与求了一个有源汇上下界可行流。

有源汇上下界最大流

这才是一般在实际应用中使用的。要求最大流，我们可以在差网络中把附加边删掉，求残量网络的最大流，再加上之前的可行流就是答案。证明可以考虑我们新找的最大流一定是平衡的，再加上原来的可行流也是可行流。

在实现上，其实不需要真的把附加边删掉，因为除了汇点连向源点的边其他的都已经满流了，对答案没有影响，因此只需删汇点连向源点的边即可。

现在再来看这道题，其实建模很朴素，源点向每一天连\([0,D_i]\)的边，
每一天向每个少女连\([L_{i,j},R_{i,j}]\)的边，每个少女向汇点连\([G_i,inf]\)的边，然后跑有源汇上下界最大流即可。

5.P4843 清理雪道

题意：求有向图最小链覆盖，每条链可以相交。

思路：一开始以为就是最小链覆盖，结果样例一直过不去，手推出来发现确实有问题，然后才发现问题。考虑建模，每条边最少被覆盖一次，于是可以源点向每个点连容量为\(inf\)的边。每个点向汇点连容量为\(inf\)的边，对于原图上的边\((x,y)\)，从\(x\)向\(y\)连\([1,inf]\)的边，然后跑有源汇上下界最小流即可。等等，这里是最小流，不是最大流，那怎么求呢？

有源汇上下界最小流

可以类比有源汇上下界最大流的做法，只是要从汇点到源点跑一遍最大流，再用可行流减去最大流就是答案。

6.P4043 [AHOI2014/JSOI2014]支线剧情

题意：DAG最小链覆盖，要求每条链的开头是1号点，有边权。

思路：一开始以为就是上一题然后改流量，结果发现有边权不好处理。于是考虑用费用流。这时就需要用上有源汇上下界费用流

有源汇上下界费用流

其实理论上是有源汇上下界最小可行费用流，也就是不一定是最大流。

具体做法其实和前面的很像。对于一条边\((u,v,[l,r],cost)\)，由建边\((u,v,r-l,cost)\)，并且把答案加上\(l\times cost\)，同样，如果\(in[i]>out[i]\),建边\((S,i,in[i]-out[i],0)\)，反之则\((i,T,out[i]-in[i],0)\)，最后建边\((T,S,inf,0)\)，再跑\((S,T)\)的最小费用流，加上之前累计的答案即可。（确实是很像）

7.P4553 80人环游世界

题意：\(n\)个城市，最多\(m\)个人，每个人可以按\(1\)~\(n\)顺序选择若干个城市依次游历，每个城市恰好被\(v_i\)个人经过，从\(i\)到\(j\)代价为\(w_{i,j}\)，求最小代价。

思路：一开始想的时候在最小费用最大流和有源汇上下界最小费用可行流之间纠结，然后写了后者，发现过不了样例，于是就去写前者，发现建模其实很简单，只是要额外建一个点表示哪些人从哪个城市开始就可以了。

8.CF277E Binary Tree on Plane

题意：平面上有\(n\)个点，要求用这些点组成一个二叉树，且每条边都是从\(y\)坐标大的点向\(y\)坐标的点，权值是两个点的欧几里得距离，求最小总权值。

思路：比较简单的费用流建模。拆点，源点向1连容量为\(n-1\)，费用为0的边，除1以外的所有点向汇点连容量为2，费用为0的边，其他每个点向可以到的点连容量为\(1\)，费用为\(dis\)的边，跑最小费用最大流，如果最大流\(\ne n-1\)，就无解，否则费用为答案。（有人写zkw一直寄但是一改成EK就过了，比较离谱）。

9.P5030 长脖子鹿放置

题意：给一个\(N\times M\)的棋盘，有一些格子是障碍，长脖子鹿按照“目”字攻击，求最多可以放多少个互不攻击的长脖子鹿。

思路：类似骑士共存问题，只是这次二分图判定标准是行（或列）的奇偶性。