$dp$维护最小割
发现最小割是每个竖列都需要割掉一条边，然后用横边把他们连起来。
$dp_{i,s}$表示当前到了第$i$列,集合$s$的竖列已经有某条边被选中了，那么转移就是枚举当前第$i$列选不选边，然后再把需要选的横边选上割掉。
复杂度$O(2^{n}nm)$
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int sz = 1 << 7, maxn = 1e5 + 5; const ll inf = 1LL << 62; int n, m; int a[maxn][6], b[maxn][6]; ll dp[sz]; int main() { scanf("%d%d", &n, &m); for(int i = 1; i < m; ++i) for(int j = 0; j < n; ++j) scanf("%d", &a[i][j]); for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) scanf("%d", &b[i][j]); for(int i = 1; i < 1 << n; ++i) dp[i] = inf; for(int i = 1; i < m; ++i) for(int s = 0; s < 1 << n; ++s) { for(int j = 0; j < n; ++j) if(!(s >> j & 1)) dp[s ^ (1 << j)] = min(dp[s ^ (1 << j)], dp[s] + a[i][j]); for(int j = 0; j < n; ++j) if((s >> j & 1) ^ (s >> ((j + 1) % n) & 1)) dp[s] += b[i][j]; } printf("%lld\n", dp[(1 << n) - 1]); return 0; }
原文：https://www.cnblogs.com/2-321414133115/p/11333773.html
