Description
众所周知，航空公司"Trouble"经常丢失行李，为此关心的记者们决定计算可能无法归还给旅客的行李最大数量。
航空公司"Trouble"在编号从 \(1\) 到 \(n\) 的 \(n\) 个机场间运营航班。记者们的实验将持续 \(m\) 天。已知在实验第一天午夜前，第 \(j\) 个机场有 \(s_j\) 件遗失行李。在第 \(i\) 天会发生以下事件：
- 早晨，同时起飞 \(2n\) 个航班，包括 \(n\) 个第一类航班和 \(n\) 个第二类航班：
- 第一类第 \(j\) 个航班从机场 \(j\) 飞往机场 \((((j-2) \bmod n )+ 1)\)（前一个机场，第一个机场的前一个是最后一个），最多可运输 \(a_{i,j}\) 件遗失行李；
- 第二类第 \(j\) 个航班从机场 \(j\) 飞往机场 \(((j \bmod n) + 1)\)（后一个机场，最后一个机场的后一个是第一个），最多可运输 \(c_{i,j}\) 件遗失行李；
- 下午，机场会进行遗失行李检查。如果当天航班起飞后，第 \(j\) 个机场剩余 \(x\) 件行李且 \(x \ge b_{i, j}\)，则至少会有 \(x - b_{i, j}\) 件行李被找到，不再视为遗失；
- 晚上，当天所有 \(2n\) 个航班结束，运输的遗失行李抵达对应机场。
对于每个 \(k\) 从 \(1\) 到 \(m\)，记者们想知道在前 \(k\) 天的检查中可能未被找到的遗失行李最大数量。注意每个 \(k\) 的计算都是独立的。
\(1\leq n\leq 12,1\leq m\leq 2000\)。
Solution
首先这个显然是网络流，有一个比较显然的最大流建模是建给第 \(i(0\leq i\leq m)\) 天建一个点 \((i,j)\) 表示这一天晚上机场 \(j\) 的行李数量，同时第 \(i\) 天有个汇点 \(T_i\)。连边就是 \((i-1,j)\) 向 \((i,j)\) 连流量为 \(b_{i,j}\) 的边，\((i-1,j)\) 向 \((i,j-1)\) 连流量为 \(a_{i,j}\) 的边，\((i-1,j)\) 向 \((i,j+1)\) 连流量为 \(c_{i,j}\) 的边，\((i,j)\) 向 \(T_i\) 连流量为 \(+\infty\) 的边。第 \(i\) 天的答案就是 \(S\to T_i\) 的最大流。
但是直接跑肯定是不行的。考虑转最小割。
由于 \(n\leq 12\) 且只有相邻层数之间的边，所以可以直接按照天数把和 \(S\) 连通的点压入状态。
设 \(f_{i,S}\) 表示前 \(i\) 天，钦定第 \(i\) 层和源点相连的点为集合 \(S\) 内的点，其余的全和汇点相连。
转移为：
注意：这里转移的边必须满足前面的点属于 \(T\)，后面的不属于 \(S\)，不能加入前面属于 \(S\) 后面不属于 \(T\) 的贡献，因为这样的边根本不会被经过！！！
直接转移是 \(O(m\cdot 4^n)\)，过不了。优化就考虑先把初始状态设为上一层的状态，然后从前往后逐位修改状态，设 \(g_{i,S,0/1}\) 表示修改了前 \(i\) 位，目前状态为 \(S\)，且第 \(i\) 位在修改前是 \(0/1\) 的最小答案。容易转移。
单次转移是 \(O(2^nn)\)。
时间复杂度：\(O(nm\cdot 2^n)\)。
Code
#include <bits/stdc++.h>#define int int64_tconst int kMaxN = 15, kMaxM = 2e3 + 5, kMaxS = (1 << 13) + 5;int n, m;
int cnt[kMaxN], a[kMaxM][kMaxN], b[kMaxM][kMaxN], c[kMaxM][kMaxN];
int f[kMaxS];inline void chkmax(int &x, int y) { x = (x > y ? x : y); }
inline void chkmin(int &x, int y) { x = (x < y ? x : y); }void dickdreamer() {std::cin >> n >> m;for (int i = 1; i <= n; ++i) std::cin >> cnt[i];for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) std::cin >> a[i][j];for (int j = 1; j <= n; ++j) std::cin >> b[i][j];for (int j = 1; j <= n; ++j) std::cin >> c[i][j];}for (int s = 0; s < (1 << n); ++s) {f[s] = 0;for (int i = 1; i <= n; ++i)if (s >> (i - 1) & 1)f[s] += cnt[i];}for (int i = 1; i <= m; ++i) {static int g[kMaxS][2], tmp[kMaxS][2];for (int s = 0; s < (1 << (n + 1)); ++s) g[s][0] = g[s][1] = 1e18;for (int s = 0; s < (1 << n); ++s) g[s | ((s & 1) << n)][s >> (n - 1) & 1] = f[s];for (int j = 0; j < n; ++j) {for (int s = 0; s < (1 << (n + 1)); ++s)for (int o = 0; o < 2; ++o)tmp[s][o] = g[s][o], g[s][o] = 1e18;for (int s = 0; s < (1 << (n + 1)); ++s) {for (int o1 = 0; o1 < 2; ++o1) {for (int o2 = 0; o2 < 2; ++o2) {int val = tmp[s][o1], t = s;if (o2 ^ (s >> j & 1)) t ^= (1 << j);val += ((o1 == 0) && (o2 == 1)) * c[i][(j + n - 1) % n + 1];val += (((s >> j & 1) == 0) && (o2 == 1)) * b[i][j + 1];val += (((s >> (j + 1) & 1) == 0) && (o2 == 1)) * a[i][(j + 1) % n + 1];chkmin(g[t][s >> j & 1], val);}}}}std::fill_n(f, 1 << n, 1e18);for (int s = 0; s < (1 << (n + 1)); ++s) chkmin(f[s & ((1 << n) - 1)], std::min(g[s][0], g[s][1]));std::cout << f[(1 << n) - 1] << '\n';}
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}