网络流做题整理

· · 个人记录

如题。整理待复习。

  1. P2517 [HAOI2010]订货

费用流不算难的一题。只是 S 这个限制需要注意。当月可以卖掉的完全不用计入限制。

从每个点向汇点连流量 u_i，费用0的边，每个月需要这些货物。从源点向每个点连流量无限，费用 d_i 的边，表示可以无限购买，但需要付费。然后从一个点向下一个对应的点连流量 S，费用 m 的边，表示仓库只能容下这些并且要Q。

跑最小费用最大流即可。

  1. P4174 [NOI2006]最大获利

挺水且套路的最大权闭合子图题。直接从每个中转站向汇点连 p_i 的边，从源点向每个要求连 c_i ，从每个要求向要求要的 a_i,b_i 中转站连无限流量的边。

用 c_i 之和减去最大流即是答案。

  1. P2172 [国家集训队]部落战争

也有点套路题的样子。如果每个点是城镇，就拆成入点和出点，从源点到入点和出点到汇点分别连流量1的边，表示最多走到一次，而且可以有一支军队从这里出发。从每个城镇的入点到其可以走到的城镇的出点连为1的边。

城镇数减去最大流就是答案。

  1. P2053 [SCOI2007]修车

get了费用流新套路。把 m 个工人分别拆成 n 个点，表示每个时段的工人，然后从 s 到每个点连流量1，费用0的边，从每个车向汇点连流量1，费用0的边，最后再从每个工人对应时段的点向对应汽车连 流量为1，费用为时段编号乘以时间 T 的边。

跑最小费用最大流，最后除以一个 n 即可。

  1. P4304 [TJOI2013]攻击装置

套路题。先黑白染色，发现一个格子可以攻击到一个不同颜色的格子。于是从源点向每个 (i + j) \% 2 == 1 且可以放置的点连流量1的边，从每个 (i + j) \% 2 == 0 且可以放置的点向汇点连流量1的边，然后从每个 (i + j) \% 2 == 1 的点连流量1的边向每一个可以走到且可以放置的点。

可以放置的地点数减去最大流就是答案。

  1. P5934 [清华集训2012]最小生成树

和生成树相关知识结合的好题。考虑到一条边权为 L 的边要可能在最小生成树上出现，然而我们最小生成树肯定优先选边权小的边，所以在选目标边之前，所有边权小于 L 的边肯定优先考虑，那么根据求最小生成树的方法，如果目标边端点 u,v 已经连通了，那么这条边肯定是不选的。

所以我们就要删掉尽可能少的一些边权小于 L 的边，使得前面的所有边选完之后，u,v 仍然不连通。这样就转化为了最小割问题，只需把所有边权小于 L 的边连起来(无向边)，边权为1，然后以 u,v 分别为源点和汇点，跑一遍最大流最小割就是答案了。

最大生成树同理。

  1. P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

依旧是套路题。直接从每个同意睡觉的小朋友向源点连流量1的边，从每个不同意睡觉的小朋友向汇点连流量1的边，在每一对好朋友之间连流量1的双向边。

最大流就是答案。

  1. P4001 [ICPC-Beijing 2006]狼抓兔子

最小割板子题。直接按照题意，把 1,1 设为源点，n,m 设为汇点，按照题意连双向边，跑最大流最小割就是答案。

  1. P2472 [SCOI2007]蜥蜴

有一(亿)点套路。从源点向每个有蜥蜴的点连流量1的边，把每个有石柱的点拆成入点和出点，它们之间连流量为高度的边。再从每个点向每个能到达的点(即距离小于等于 d)连流量无限的边。然后如果能跳出地图就向汇点连边权无限的边。

最大流就是答案。

  1. P2774 方格取数问题

和5.一样，黑白染色套路题，只不过除了相邻不能取数没有其他取数限制，于是和5.一样，源点--黑点数值-->黑点--无限-->取了这个黑点会被限制不能取的白点--百点数值-->汇点，所有数字之和减去最大流即可。

  1. P3324 [SDOI2015]星际战争

虽然也是网络流，但是多了点东西，需要二分答案，每次二分的时间看是否够打完全部机器人，够就 r = mid，否则就赋值给 l。然后从源点向激光武器连这个武器每秒攻击点数值乘以时间点变，从每个机器人向汇点连耐久值点边，最后将可以攻击的每对机器人和激光武器连无穷大点边，跑最大流看够不够打即可。

注意精度要求，可以将每个机器人生命值先乘以一万，最后时间再除以一万输出，这样就可以用整数了。开long long。

  1. P2604 [ZJOI2010]网络扩容

很水的一个题吧。对于第一问直接跑最大流计算，第二问进行费用流，先按原图点流量和方向建边，费用为0，再在原图每一条边点基础上连流量无限，费用为 w 点边，最后从点 n 到汇点连一条流量 maxflow +k 点边，跑费用流即可。

13.[POJ 114]卖猪问题

题意：有 m 个猪圈，每个猪圈里有 C_i 只猪，n 个人想要先后买猪的人，第 i 个人只可以买 A_{i,j} 共 k 个猪圈里的猪，第 i 个人最多买 B_i 只，每个人来买的时候可以调换猪圈里的猪，客人的先后顺序不能调换，求能卖出的最大猪数。

解法：从源点向每个第一个购买 i 猪圈的人连猪数 C_i，从每一个购买 i 猪圈的人向下一个人连无穷流量的边，再从每一个人向汇点连 B_i 的边。