网络流好毒瘤 qwq

最大流

  • 20/11/21 P3376 【模板】网络最大流 学习最基础的网络流
  • 20/11/22 P1343 地震逃生 最大流模板
  • 20/11/23 P3153 舞会 最大流 + 二分答案 https://imyangty.com/oi/1218
  • 21/02/02 P3254 圆桌问题

源向单位连大小为单位人数的边,餐桌向汇连大小为餐桌人数的边,每个单位连每个餐桌,跑最大流,满流有解,找流有东西的边输出即可

  • 21/02/02 P2763 试题库问题

试题向属于的类型连 1,类型向汇连需要的题数,跑最大流,满流有解,输出方案。

  • 20/02/02 P2891 [USACO07OPEN]Dining G

拆点,源->食物->牛in->牛out->饮料->汇,保证流过牛的流量为 1,跑最大流即可

  • 21/02/04 P2766 最长不下降子序列问题

第一问使用 n^2 dp,然后拆点处理第二问和第三问。

  • 21/02/07 P2764 最小路径覆盖问题

从每个路径长度为 0 开始想,此时有 n 条路径,然后考虑合并两个相邻的路径,发现每次合并都会造成路径个数减一。所以考虑使用网络流来做这件事情。

建源汇,拆点成入和出,源连向所有的入,所有的出连向汇,对于原图的每一条边将入连向出。所有的边容量都是 1,这样就可以跑出新图的最大匹配,使用原图的点数减去即可

  • 21/02/07 P2765 魔术球问题

上题的加强版,考虑把每个柱子都看成一条路径,然后每个点像上题一样连边。从小到大枚举答案,在残量网络上跑 Dinic 跑出增加的流量,判断是否可行,然后像上题一样输出路径。

需要注意数组一定要开够,往大了开绝对不会出问题,然后注意点编号的映射

  • 21/02/07 P2754 [CTSC1999]家园 / 星际转移问题

对于每天每个太空站都建点,枚举天数逐天加飞船边判断能流多少,流到了就成功了。一开始先用并查集判无解的情况。

费用流

  • 20/11/23 P3381 【模板】最小费用最大流 学习基础费用流
  • 21/02/07 P4015 运输问题

基础费用流,第二问求最大费用时直接重新建图,把所有费用取反相反数然后求出的最小费用取相反数就是最大费用。

  • 21/02/07 P4016 负载平衡问题

不用拆点,源向每个点连对应初始货量的边,费用为 0,每个点向汇连对应最后要达到的边,费用为 0,相邻两个点之间连双向边,容量无限,费用 1,跑费用流即可。

  • 21/02/08 P2770 航空路线问题

先逆向看问题,把问题转化为找到两条从左到右不相交的路径,然后在航线连边,费用 1,容量 1。拆点。每个入点向出点连容量 1,费用 0,特别地,最左和最右连的容量为 2(因为要走两次),跑最大费用最大流。最大流为 2 说明有解,城市数即为费用;最大流为 1 时特判航线从最左直飞到最右的情况即可。

  • 21/02/08 P4014 分配问题

二分图最大权完美匹配,KM 和费用流均可过。

  • 21/02/08 P4013 数字梯形问题

拆点 + 费用流。第一个子任务对应的是所有边容量为 1,第二个把原点与拆点之间的容量改成 inf,同时把最后一排到 t 的容量改为 inf,第三个直接把剩余除了 s 到第一排的都改为 inf 即可。原点与拆点间的费用为点权,剩余费用为 0。跑最大费用最大流。

  • 21/02/09 P3358 最长k可重区间集问题

所有重复了的区间最多被选择 k 次,所以考虑流量为 k 寻找费用流解法。离散化每个端点,然后从左到右连流量无限费用 0 的边,然后对于每个区间从左往右连流量为 1 费用为区间长度的边。跑最大费用最大流。

  • 21/02/16 P3357 最长k可重线段集问题

和上题基本类似,我们会发现只需要投影到 x 轴上做并判断与 x 轴垂直的线段即可。考虑将每个端点横坐标乘以二,对于 (x_1, x_2) 类型的我们再将 x_1 + 1,对于 (x,x) 类型的变为 (x, x + 1),不难发现这样可以轻松处理垂直的线段。

  • 21/02/16 P4012 深海机器人问题

比较简单的费用流。对于网格内每个能走的路径建两条边,一条表示取海洋生物,一条不取。源向每个起点连,每个终点连向汇。跑最大费用最大流即可。

  • 21/02/16 P1251 餐巾计划问题

非常清奇的建模。显然把每天拆成早上和晚上,每天晚上都会获得 r_i 条脏餐巾,所以源向第 i 天晚上连边,同理,每天早上都会送出去 r_i 条干净餐巾,所以往汇连。购买操作从源买即可,算起费用,洗餐巾的操作同理。

最小割

  • 21/02/18 UVA1660 电视网络 Cable TV Network

考虑枚举不连通的两个点,作为源和汇。然后拆点,连容量为 1 的边,再把原来的无向图的边化为出点到入点容量为 inf 的边,跑最大流就可以求出最小割,最小割即为容量为 1 的边数——去掉的点数。如果最小割为 inf 说明没办法使图不连通。

上下界网络流

  • 21/02/06 LOJ#115. 无源汇有上下界可行流

无源汇有上下界可行流,考虑低保网络和增量网络,为了使增量网络和低保网络会在一起之后流量守恒,需建虚拟源/汇使得多了的流量有归宿

  • 21/02/06 LOJ#116. 有源汇有上下界最大流

转换模型,从原来的 ts[0,+\infty) 的边,保证源汇点流量平衡,然后就可以找到一个可行流(这个可行流的流量即为 <t,s> 的流量。之后在残量网络上跑从 st 的最大流榨干剩余的流量即可。

  • 21/02/06 P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

源向每天连 [0,D_i] 的边,每天向对应的每个少女连对应 [L,R] 的边,每个少女向汇连 [G_i,+\infty) 的边,然后跑有源汇上下界最大流

最后修改日期:2021年2月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。