A. 奇怪的游戏

网格图在网络流中往往对应着黑白染色，当然还有四色染色等奇怪的东西。

建图并不难，但是二分的思想是很好的。

考虑如何检验一个答案$x$，将黑点视为二分图的左部点，白点视为二分图的右部点。

一次操作对应一组相邻黑白点$+1$，所以直接建图看能否跑满流就完了。

然而需要注意，显然仅当黑点数=白点数时，答案具有单调性。

然而对于黑点数不等于白点数，答案只可能为一个固定值，只要检查单点就可以了。

B. 士兵占领

对于行列关系的建图，可以分别将行列放在二分图的两侧，行列连边表示行列的交点。

题中的限制为至少，所以可以用上下界最小可行流来解决。

利用本题并没有规定上界，一个更好的解决办法是将至少放置转化为至多放置，

即考虑删掉点的过程，这样可以直接用流量进行最大的限制。

C. 紧急疏散evacuate

似乎是一个常见的套路，将原图中的节点按不同的状态拆分。

在本题中可以表现为每个时间拆点，然后可以直接建边就好了。

本题可以通过二分答案来确定答案的大小，另一个好打的（或许也会更快）做法是直接在残量网络上加点/加边。

D. 狼抓兔子

最小割可过。

当然正解是平面图转对偶图，

将平面图割出的每个块视作对偶图中的一个点，

在块之间建边，边权即分割两个块的边的流量。

这个东西蛮好理解的（尤其是双向边流量相同时），画画图就好了。

E. 切糕

同一行列必须选一个点，所以将点连成一串解决。

相邻两个点的限制为距离不超过$d$。

考虑$inf$边$(a,b)$的作用为$s->a$或$b->t$必须割一个。

所以对于有限制的（即相邻的）每个点对$(i,j)$，从$i$的第$k$个副本，向$j$的第$k-d$个副本连$inf$边就好了。

F. Figure Eight

因为复杂度允许$O(n^3)$，

单调指针维护每个区间对应的最大长度，

然后区间$dp$统计一下就好了，求大神教我网络流做法。

G. 最大获利

选择两个点，对应一个收益。

算是个最简单的最大权闭合子图。

因为收益次数并不多，对每个收益新建一个点，连一些$inf$边就好了。

H. happiness

还是一道最大权闭合子图题，然而两侧对应了不同的选择。

因为收益次数并不多，对每个收益新建一个点，连一些$inf$边就好了。

I. employ人员雇佣

还是一道最大权闭合子图题，然而二者一个选而一个不换会对应一个损失。

这个时候我们可以向$DC$大神学习解方程技巧，通过奇怪的边权来因为收益次数并不多，对每个收益新建一个点，连一些inf边就好了。

因为收益次数很多，对每个收益新建一个点的做法$T$掉了。

这个时候就可以学习大神的技巧，在造成收益的点$(i,j)$之间建边。

具体来说，将每个点分别连$s$，$t$，流量分别为该点造成的收益和，选择该点的花费。

割两个方向分别代表着不选/选。

这样对于$(i,j)$均选，$(i,j)$均不选的收益都是正确的。

对于$(i,j)$只选一个，会导致收益多获得了一份/损失没有统计，所以在$(i,j)$ $(j,i)$之间连边$2*val_{i,j}$就可以统计这一份贡献。

J. 不同的最小割

似乎是一个名为最小割树的数据结构。

算法流程大概是：

初始集合为全部点集。

每次任取集合中的两个点$a$ $b$，跑出二者之间的最小割。

在$a$ $b$之间建边，为最小割的权值。

$S$ $T$一定不联通，将$S$ $T$两个集合分别进行分治就好了。

最终任意两点的割，对应着两点树上的割，即唯一路径的最小边权。

这个玩意就并不会证明，但是结论好背，代码好打。

K. 晨跑

直接拆点限制点的流量，费用流。

L. 80人环游世界

裸的上下界最小费用可行流。

然而做到这里的时候并不会这个优秀的算法。

所以乱搞出了一个奇怪的算法。

给一些边权加上$-inf$，这样在最小费用的前提下一定会流满这条边，然后问题就解决了。

$HErk2$ $kx$大神告诉我，这个做法就很没有拓展性，就很$five$。

然而$cbx$告诉我，对于上下界费用流，只要对下界部分用这个做法，上下界之间的部分用普通流就好了，大神告诉我这个做法就很帅。

因为大神$cbx$>$rk2$，显然$cbx$大神是对的。

M. 修车

刚开始考虑的是正向考虑，即正常人的思维方式，然后这个图就很不可建。

正解的做法是逆向考虑，倒数第$k$辆修的车，只造成了$k$倍修车时间的贡献。

所以将每个修车师傅拆为$n$个点，分别表示修的倒数第$k$辆车就好了。

N. 数字配对

又是一类套路题？

配对问题往往利用一些特殊性质，

划分为二分图的形式，分别连在$s$，$t$上，之间连边就好了。

该题中的划分表现为质因子个数的奇偶性。

O. 美食节

与《修车》一题的建图就比较类似，然而暴力建图必死。

然而本题中拆点的限制就表示，当倒数第$k$辆车还没修时（假设修车=做菜），倒数第$k+1$辆车是没用的。

所以在增广到某师傅修倒数第$k$辆车的节点的时候，新建第$k+1$个节点副本就好了。