\((u, v, c, w)\) 表示 \(u \to v\)，容量 \(c\)，费用 \(w\)。
QOJ 130
暴力增广，每次求二次函数极值即可。
QOJ 665 / 7762
这其实是一个类似最小路径覆盖的问题，因此我们考虑先加入所有代价，然后尝试删掉尽量多的操作代价。
建图有很多方法，以下介绍一种我用的做法。
不妨假设 \(a_j\) 相邻不同，建立 \(K\) 个点 \(T_1, T_2, \dots, T_{k-1}, T_K=T\) 和源点 \(S\)。连边：
连边 \((S, T_1, M-1, 0)\)。
对于 \(i=1,2,\dots,K-1\)，连边 \((T_i, T_{i+1}, +\infty, 0)\)。
对于 \(1 \le i < j \le K\) 满足 \(a_i = a_j\) 且 \(a_{i+1}, \dots, a_{j-1} \ne a_i\)，连边 \((T_{i+1}, T_j, 1, -w_{a_i})\)。
意思是，对于不需要在后面继续利用的球，我们不妨单独分出一个盒子专门放它们。于是剩下你可以有 \(M-1\) 个盒子用来处理掉一些代价（注意没有相邻相同，因此这个限制是紧的）。
跑 \(S\) 到 \(T\) 的最小费用最大流即可。
QOJ 1197
第一个观察是，我们可以先涂黑色的线，再涂白色的线，然后剩下的是否要涂是唯一确定的。
另一个观察是，每个点，每个方向只需要涂一次，即便颜色不同。颜色相同时是显然的，颜色不同时在上面的一定是白色，也有办法用底色替代。
考虑 01 变量 \(bh_{i,j}, bv_{i,j}, wh_{i,j}, wv_{i,j}\) 表示是否将 \((i, j)\) 在水平 / 垂直方向涂成黑 / 白色。
然后我们来刻画一下代价：
对每个格子 \((i, j)\)，有代价 \(\infty \cdot (bh_{i, j} \cdot wh_{i, j} + bv_{i, j} \cdot wv_{i, j})\)。
涂黑色水平线的代价是 \(a \cdot \sum_{i, j} bh_{i, j} + b \cdot\sum_{i, j} bh_{i, j} \cdot \overline{bh_{i, j+1}}\)。类似地也有其他三种代价。
单独涂黑色格子 \((i, j)\) 的代价是 \(c \cdot \overline{bh_{i, j}} \cdot \overline{bv_{i, j}} + \infty \cdot (wh_{i, j} + wv_{i, j})\)。
单独涂白色格子 \((i, j)\) 的代价是 \(c \cdot (bh_{i, j} \cdot \overline{wv_{i, j}} + bv_{i, j} \cdot \overline{wh_{i, j}}) + \infty \cdot bh_{i, j} \cdot bv_{i, j}\)。
然后我们把 \(bv, wh\) 反转，那么每一项都是交叉项，可以变成最小割。
QOJ 1359
首先点拆边，点数变为 \(2n\)。转化成一些边可以选择安装地图。然后考虑每个点有一个 \([0, k]\) 的整数变量 \(f_u\) 表示 \(S\) 到 \(u\) 最少要经过多少个地图。
一条边 \((u, v)\) 如果不能放地图，那么要求 \(f_v \le f_u\)；如果可以放地图，那么可以选择 \(f_v \le f_u+1\)，但是会有 \(C_{(u, v)}\) 的代价。
考虑改为定义 \(2n(k+1)\) 个 0/1 变量 \(g_{u, j} = [f_u \ge j]\)。那么有以下的代价：
- 基本限制 \(\infty \cdot \overline{g_{u, 0}} + \infty \cdot \sum_j g_{u, j} \cdot \overline{g_{u, j-1}}\)。
- 基本限制 \(\infty \cdot g_{S, 1} + \infty \cdot \overline{g_{E, k}}\)。
- 对于不能放地图的 \((u, v)\)，有 \(\infty \cdot \sum_j \overline{g_{u, j}} \cdot g_{v, j}\)。
- 对于可以放地图的 \((u, v)\)，有 \(C_{(u, v)} \cdot \sum_j \overline{g_{u, j}} \cdot g_{v, j} + \infty \cdot \sum_j \overline{g_{u, j-1}} \cdot g_{v, j}\)。
构造方案也不难，只需要检查哪些 \((u, v)\) 满足存在 \(\overline{g_{u, j}} \cdot g_{v, j} = 1\) 即可。
QOJ 2208
仔细思考容易发现这其实是最大费用循环流，进一步左右部点可以合并，因此先假设所有边都满流然后调整即可。
QOJ 3299
我们容易扩展 Hall 定理猜到条件是对于任意集合 \(S\) 满足 \(\sum_{i\in S} a_i \le \sum_j \min(b_j, |S|)\)。
直接维护 \(f_k = \max_{|S|=k} \left(\sum_{i\in S} a_i - \sum_j \min(b_j, |S|)\right) = \max_{|S|=k} \sum_{i\in S} a_i - \sum_j \min(b_j, k)\)。
注意到 \(a, b\) 的修改只有 \(\pm 1\)，对 \(f_k\) 的影响也只是区间 \(\pm 1\)，线段树即可。
QOJ 4630
把用 Dinic 多路增广的 Primal-Dual 搬出来，过了，咋回事？
这是显然的，因为最短路总是不小于 \(-5\)，每轮增广是 \(O(m \sqrt n)\)，而当最短路到 \(0\) 的时候就可以退出了。
QOJ 5048
考虑每次取出外围的边中最小的，考虑其所在的内部面，结合对偶图最短路容易证明在任意最小割中该面一定经过 \(0\) 或 \(2\) 条边。
那么我们将这条边删去，将容量加到同一个面的其他边上即可。
直到剩下一棵树，我们知道原图的最小割与该树的最小割等价，于是它便是原图的最小割树，Kruskal 即可。
QOJ 6308
操作可以转化成维护 \(01\) 序列 \(b_1, \dots, b_n\)，每次将 \(b_l, b_r \gets 1\)，\(b_{l+1}, \dots, b_{r-1} \gets 0\)，最大化 \(1\) 的个数。
考虑任意两个区间的关系，如果是包含或相离，那么互相不会影响。如果是相交，那么会出现矛盾。可以证明只要不存在相交就一定合法。
二分图最大匹配即可。
QOJ 6508
不妨将题意弱化成子图的各个点度数 \(\le 2\)，首先最小化孤立点个数，然后最小化二度点个数即可。容易知道最优解一定没有长度 \(> 3\) 的链。
因此取一个较大数 \(M\)，给每个点连两条边，容量均为 \(1\)，费用分别为 \(-M, 1\)，然后跑最小费用流（不必最大）即可。
掏出 Dinic 实现的 Primal-Dual 即可。