1.bzoj狼抓兔子 最大流=最小割

2.网络流24飞行员配对方案问题 二分图最大匹配

S向正驾驶员连边，容量1，副驾驶员向T连边，容量1，正驾驶员向可配合的副驾驶员连边，容量1，求最大流

3.codevs骑士共存问题 最大独立集

首先把棋盘黑白染色，使相邻格子颜色不同。把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。从S向X集合中每个点连接一条容量为1的有向边，从Y集合中每个点向T连接一条容量为1的有向边。从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。求最小割，结果就是可用格子的数量减去最小割。

4.noi最大获利 最大获利转最小割

S与人连边，容量为获利。站点与T连边，容量为耗资，人与其需求的站点连边，容量为无穷。

找最小割，即割边上的值便为不能获取的利润值，用总值减去得出最大利润。

5.JoyOI棋盘覆盖 codevs覆盖

我们可以对棋盘进行染，黑白相间，即相临两格不同色，这样染完色，我们就可以将同种颜色的格子作为一个集合，另外一种颜色作为一个集合，然后相邻格子间存在边的关系   （当然得排除挖去的部分）。求二分图最大匹配。

6.JoyOIQQ农场 最大点权独立集

黑白染色，S到X集合中的点边容量为该点权值，Y到T同，不能同时取的两个格子连一条无穷大的边，结果是所有格子权值和减去最小割

7.codevs方格取数3 最大点权独立集

8.bzoj网络扩容

9.bzoj蜥蜴

对于每根石柱，采取一分为二的想法，即把一个点分为两个点（可抽象为石柱底部到顶部），其连线容量限制为石柱高度。

S与所有有蜥蜴的点相连，容量为1。

地图内所有能跳出的点与T相连，容量为INF。

对于地图内任意两个石柱，如果间距小于d，就将其中一根石柱的顶部与另一根石柱的底部相连，其连线容量为INF。

构图完成，剩下就是跑一遍最大流，然后用蜥蜴数量减去最大流就是最终结果。

10.codevs方格取数2 费用流+拆点

把每个格子拆成两个点 a2=a1+n*n，a1向a2连一条容量1费用为点权的边，一条容量INF费用0的边

若a能到达b，则a2向b1连一条容量k，费用0的边

S向1连一条容量k，费用0的边

n*n*2向连一条容量k，费用0的边

最大费用流

11.codevs蚯蚓的游戏问题 费用流+拆点

和方格取数基本相同，S向第一层所有点连边，最后一层所有点向T连边

12.codevs数字梯形问题

将蚯蚓的游戏略加改动

1、与蚯蚓的游戏规则一完全相同

2、规则二，由于可以共点，所以就不用拆点了，源点与上层继续保持容量为1，并一将底层与汇点的容量限制改为无穷大即可，其它类似，

3、规则三，由于边和节点都可以共用，此时没有必要把原网络销毁，直接在上一个规则的前提下修改每一条边的容量即可（注意源点与顶层节点之间的容量还是1，否则就无法满足是m条路径取得的最大值，其他边的容量改成无穷大即可）

13.bzoj晨跑

费用流+拆点

14.JoyOI武器分配

每人一个机枪一个防弹衣，就像是一个二分图最大匹配，所以直接在所有机枪和所有防弹衣之间连上有向边，边的费用为(a[i]-b[j])^2，容量为1。

再加上超级源和超级汇，费用为0，容量为1。

最后再加一个第二汇点，超级汇和第二汇点相连，费用为0，容量为n，进行人数限制。

最后来一次最小费用最大流就可以了。

15.网络流24最小路径覆盖问题

将每个点都分别放入xy集合中

如果u到v有一条边,则x集合的u向y集合的v连一条权值inf的边

S向x集合的点连边，权值1，y集合的点向T连边，权值1，做一遍最大流，得出最大匹配数

ans=n-最大匹配

如果无匹配，显然要n条路径才能覆盖所有点，两个点匹配意味着将可以把它们用一条路径覆盖，路径数就可以减1

16.bzoj紧急疏散

对于每个门进行一次bfs，得出每个点到每个门的时间

然后二分时间，每次建图dinic

S到空地连一条容量1的边，每个空地到可到达的门连一条容量1的边，每个门到T连一条容量为时间的边

17.网络流24运输问题

1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。

求最小费用最大流，最小费用流就是最少运费，求最大费用最大流，最大费用流就是最多运费。

17.网络流24魔术球问题

枚举答案A，在图中建立节点1..A。如果对于i<j有i+j为一个完全平方数，连接一条有向边(i,j)。该图是有向无环图，求最小路径覆盖。如果刚好满足最小路径覆盖数等于N，那么A是一个可行解，在所有可行解中找到最大的A，即为最优解。

具体方法可以顺序枚举A的值，当最小路径覆盖数刚好大于N时终止，A-1就是最优解。

18.网络流24圆桌聚餐

1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。

2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。

3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。

求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。

19.bzoj跳舞

先把每个人i拆分成ix和iy两个节点，ix连向喜欢的人，iy连向不喜欢的人，容量为1（比如如果男生i与女生j互相喜欢，则由ix连向jx，如果男生i与女生j互相不喜欢，则由iy连向jy），再将每个男生男生ix连向iy，容量为k；每个女生iy连向ix，容量为k。由源点向每个男生的x节点连上一条边，再由每个女生的x节点向汇点连上一条边，容量均为a。最后从小到大枚举a，计算最大流flow，若发现a*n>flow(不满流)，则停止枚举，a-1即为答案。

或者可以二分

20.网络流24餐巾计划

这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。

经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m)，费用为f，送到慢洗部(Xi->Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。

21.bzoj善意的投票

构建源S,汇T
然后S->一开始投同意的xpy,一开始投反对票的xpy ->T
流量均为1
然后对于一个朋友关系(a,b) 添加双向边，流量依然为1
最后割即为冲突数
(1) 冲突数不大于 n:
很显然，哪怕所有xpy之间都存在朋友关系，xpy可以通过改变(或不改变)原先的决定到达全“同意”或全“否定”，那么朋友之间的冲突数为0，而未被自己先前决定的冲突数不大于n
(2) “同意”集合和“否定”集合之间的边全部是朋友关系
(3) 冲突是同意与不同意之间的割

22.网络流24负载平衡问题

计算出每个仓库的盈余后，可以把问题转化为供求问题。建立供求网络，把二分图X集合中所有节点看做供应节点，Y集合所有节点看做需求节点，在能一次搬运满足供需的Xi和Yj之间连接一条费用为1的有向边，表示搬运一个单位货物费用为1。另外还要在Xi与相邻的Xj之间连接边，表示货物可以暂时搬运过去，不立即满足需求，费用也为1。最大流满足了所有的盈余和亏损供求平衡，最小费用就是最少搬运量。

23.网络流24分配问题

把所有人看做二分图中顶点Xi，所有工作看做二分图中顶点Yi，建立附加源S汇T。

1、从S向每个Xi连一条容量为1，费用为0的有向边。
2、从每个Yi向T连一条容量为1，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为Cij的有向边。

求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。

24.JoyOI任务分配

源点向所有管理员连d[i]的边

管理员向可解决的任务连1的边

任务向汇点连1的边

ans=m-最大流