P4249
双倍经验 CF1264E，后续把三元组全部看成无序。
一个三元环与三个点有关，如果转而统计不合法的三元组，一定恰存在一个 \(u\) 使得 \(u \to v\) 以及 \(u \to w\) 的边都存在。因此若 \(u\) 的出边条数为 \(deg_u\)，其对答案的贡献为 \(deg_u(deg_u-1)/2\)。
当度数增加 \(1\) 时，对答案贡献 \(deg_u-1\)。因此对于 \(u\) 向汇点连边权为 \(deg_u-1 \sim n-2\) 的边，相当于差分建图。
一条未出现的边相当于给 \(u\) 或 \(v\) 的度数增加一。
因此 \(u\) 对汇点连 \(n-1-deg_u\) 条费用为 \(deg_u-1 \sum n-2\)，流量为 \(1\) 的边，对于每条未出现的边，新建 \(x\)，\(u \to x,u \to y\) 流量为 \(1\)，费用为 \(0\)，源点到 \(x\) 流量为 \(1\)，费用为 \(0\)。
算是很巧妙的拆贡献，无论是把贡献放到 \(u\) 还是差分建图。
int main() {
int n; scanf("%d", &n);
std::vector<std::vector<int>> a(n, std::vector<int>(n, 2));
std::vector<int> deg(n);
int s = n, t = n + 2, ans = 0;
MF S(n + 3 + n * n, s, t);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
scanf("%d", &a[i][j]), deg[i] += (a[i][j] == 1);
a[i][i] = 0, ans += deg[i] * (deg[i] - 1) / 2;
for (int j = deg[i]; j < n; j++)
S.link(i, t, 1, j);
}
int cnt = n + 2;
std::vector<std::vector<int>> id(n, std::vector<int>(n, -1));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) if (a[i][j] == 2) {
S.link(s, id[i][j] = ++cnt, 1, 0);
S.link(id[i][j], i, 1, 0);
S.link(id[i][j], j, 1, 0);
}
}
ans += S.mcmf().second;
printf("%d\n", n * (n - 1) * (n - 2) / 6 - ans);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) if (id[i][j] != -1) {
int x = S.e[id[i][j]][1].v, y = i + j - x;
if (!S.e[id[i][j]][1].w)
a[x][y] = 1, a[y][x] = 0;
else
a[y][x] = 1, a[x][y] = 0;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%d ", a[i][j]);
printf("\n");
}
}
P4174
双倍经验 CF1082G。
考虑在一张二分图上跑最小割。最小割模型形如：左边和右边中至少一边产生贡献。
考虑在左边放代价，右边放贡献。则若贡献被选中，则所有代价都不必付出；若所有代价都付出，则贡献可以不被选中。取反，让右边被割表示无贡献，不割表示有贡献，则若有贡献，则所有代价都必须被付出（右边没有被割断）；若无贡献，则左边随意。
显然这道题可以这样做。
每个物体只有两种状态，要么选，要么不选；
给定所有物体被选择的状态，则问题能够得到唯一的答案。
感性理解，如果某个组在代价处就已经割断了，通过最小割，我们增加了代价，但保住了收益，如果割掉收益，说明这个组的收益不优，宁愿不要它，于是抵消了收益，但没有代价。
int main() {
int n, m; scanf("%d %d", &n, &m);
std::vector<int> a(n);
int s = n + m, t = n + m + 1;
MF S(n + m + 2, s, t);
LL ans = 0;
for (int i = 0, x; i < n; i++) {
scanf("%d", &x);
S.link(s, i, x);
}
for (int i = n, u, v, w; i < n+m; i++) {
scanf("%d %d %d", &u, &v, &w), --u, --v, ans += w;
S.link(i, t, w), S.link(u, i, inf), S.link(v, i, inf);
}
printf("%lld\n", ans - S.mf());
}
P1251
费用流，大小为 \(1\) 的流代表一张餐巾。
买餐巾：\(s \to i\) 连大小正无穷，单位费用为 \(p\) 的边。
新餐巾和旧餐巾不能混用，于是拆点，把旧餐巾和新餐巾拆成两个点。
一天用过的餐巾会变旧，因此拆成早晚的点。
旧餐巾可以沿用，因此晚上的旧餐巾连第二天晚上的旧餐巾。
早上多余的新餐巾事实上不优，因为每天购买餐巾的钱一样。所以可以看成早上只有新餐巾，晚上只有旧餐巾。因此每天晚上向 \(x\) 天后早上连边，容量无限，表示去洗。
每天需要有 \(r_i\) 张餐巾，因此每天早上向汇点连容量为 \(r_i\) 的边。同时，每天会产生 \(r_i\) 张旧餐巾，因此每天从源点连 \(r_i\) 的边到晚上。
拆早晚的想法非常厉害，尤其是把旧餐巾看作产生的一种东西，分开看新餐巾被送往汇点、旧餐巾从源点产生。
int main() {
int n; scanf("%d", &n);
std::vector<int> r(n);
for (int &x : r) scanf("%d", &x);
int p, m1, f1, m2, f2;
scanf("%d %d %d %d %d", &p, &m1, &f1, &m2, &f2);
int s = 2 * n, t = s + 1;
MCMF S(2 * n + 2, s, t);
for (int i = 0; i < n; i++) {
int x = 2 * i, y = x + 1;
S.link(s, y, r[i], 0), S.link(x, t, r[i], 0);
S.link(s, x, inf, p);
if (i + m1 < n) {
S.link(y, 2 * (i + m1), inf, f1);
}
if (i + m2 < n) {
S.link(y, 2 * (i + m2), inf, f2);
}
if (i + 1 < n)
S.link(y, y + 2, inf, 0);
}
printf("%lld\n", S.mcmf().second);
}