网络流刷题日记

网络瘤刷题日记

[模板] 网络流相关/最大流ISAP/费用流zkw

分咕线

---

最大流

1. POJ 2455-Secret Milking Machine
   • 网络流路径计数, 对每条边建一条容量为1的边, 跑最大流
2. POJ 1149 PIGS: 规划最多的猪数
   • 流量代表猪的个数
3. JOJ 2453 Candy: 分配糖, 求能否使(forall i, sum_{j=1}^n a_{ij}c_{ij} ge b_i)
   • (a_{ij}=1)的糖任意分, 因此只考虑 (a_{ij}=2)
   • 利用网络流求最多分出多少 (a_{ij}=2) 的糖
   • 具体的, 对于糖 (X_i), 连((S,X_i,1));对于孩子 (Y_j), 连((Y_j,T,left lfloor frac{b_i}2 ight floor)) ; 对于(a_{ij}=2), 连 (X_i, Y_j, 1)
   • 若(maxflow+n ge sum bi), 则可行
4. ZOJ 2760 How Many Shortest Path: 不相交最短路计数
   • 求s-t最短路图, 然后直接最大流
5. SGU 438 The Glorious Karlutka River: 动态图最大流.
   • sgu438-The_Glorious_Karlutka_River
6. SPOJ 962 Intergalactic Map: 给定图与点 (A,B,C) , 求是否存在不相交路径 (A o B o C)
   • 将(B) 点设为原点, (A, C) 为汇点, 跑最大流.

最小割

1. ZOJ 2532 Internship: 求哪些边满足如果该边容量增大, 那么最大流增大.
   • 求最大流, 然后在残余网络上从 (s,t) 分别dfs.
   • 如果一条残余容量为0的边 ((u,v)) 满足 (s) 能到达 (u) 且 (v) 能到达 (t), 那么它就是一个解.
   • 判断最小割唯一性:
     • 如果存在一个点 (p) 满足 (s) 不能到达它, 它也不能到达 (t), 那么它的入边和出边一定分别是一个最小割方案. 即最小割不唯一.
2. SPOJ 839 Optimal Marks
   spoj 839-Optimal Marks

费用流

1. 费用和流量平方成正比(或下凸函数):

   • 对边权与流量差分

2. HOJ 2739 The Chinese Postman Problem: 带权有向图上的中国邮路问题

3. POJ 3680 Intervals: 区间k覆盖 (开区间)

   • 离散化
   • 对于带权值区间 ((l,r,v)), 连边 ((l,r,1,v)); 对于所有点, 连边 ((p,p+1,k,0)), 其中起点连向第一个点, 最后一个点连向终点.
   • 最大费用最大流即为答案

4. luogu1251 餐巾计划问题

5. BZOJ2597 WC2007剪刀石头布: 竞赛图, 其中一些边未定向, 定向最大化三元环个数.

   • 发现三元非环一定有一个点出度为2, 可以唯一确定这个三元环
   • 得到三元环个数: (ans = inom{n}{3} - sum_{i=1}^n inom{out_i}{2} = c - sum_{i=1}^n out_i^2), 其中c为只与 (n), (m) 有关的数.
   • 只需最小化后者; 平方费用流即可.

上下界网络流