题目大意
(n imes m) 的网格图 要求你求一个大小为 (k) 的最小权匹配。
(n leq 40000,m leq 4,k leq frac{nm}{2})
多组数据 数据组数 (T leq 1000)，保证只有三组数据 (n > 100)。
题解
首先这个题是可以二分图染色跑费用流的。所以设 (w_i) 表示 (i) 条边的答案。很容易有 (w_i-w_{i-1} leq w_{i+1}-w_i) （跑的是最小费用流 越往后增加一次费用肯定越多）
所有能建出费用流的问题基本上都是凸的
所以我们可以先 wqs 二分一发去掉大小的限制。
然后就是一个经典问题：网格图最小权匹配。写个轮廓线 dp 就行了。
dp 就设 (f_{i,j,S}) 表示考虑到((i,j)) 这个点 它上面的轮廓线的状态是 (S) 转移的时候看看这个点左边的和上边的边是否选就好了。
但是插头 dp 很难调（对我来说），所以我说下我的错误：
- 边界情况 特别是在换行的时候 因为我是把多出来的放在最后一位 换行的时候需要操作一下
- 不要漏掉边 我一开始写的程序漏掉了最上面的边
- wqs二分边界：这个题斜率的取值范围到 (frac{nm}{2}10^9) 而不是 (10^9)，因为考虑在增广过程中一条 (1) 与(10^9)的交错链 增广一次会让所有的 (1) 都切换到 (10^9) 会增加好多。（所以 wqs 二分看边界要看原问题的最大斜率 而不是感性理解）
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(register int i = a;i <= b;++i)
#define ROF(i,a,b) for(register int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 4e4+5;
const int MAXM = 5;
int R[MAXN][MAXM],D[MAXN][MAXM];
int n,m,k;
LL f[2][(1<<MAXM)+2],inf;
int g[2][(1<<MAXM)+2],now;
inline char nc(){
#define SIZE 1000000+3
static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
if(p1 == p2){
p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
if(p1 == p2) return -1;
}
return *p1++;
#undef SIZE
}
template <typename T>
inline void read(T &x){
x = 0;int flag = 0;char ch = nc();
while(!isdigit(ch)){
if(ch == '-') flag = 1;
ch = nc();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + (ch^'0');
ch = nc();
}
if(flag) x = -x;
}
inline int chk(LL ext){
CLR(f[0],0x3f);CLR(g[0],0);now = 0;
inf = f[0][0];
f[0][0] = 0;
FOR(i,0,n-1){
FOR(j,0,m-1){
CLR(f[now^1],0x3f);CLR(g[now^1],0);
FOR(S,0,(1<<(m+1))-1){
if(f[now][S] == inf) continue;
// 竖着的边
if(i != 0 && !((S>>j)&1) && !((S>>m)&1)){// !优先级很高 放在最外边
int nxt = S;nxt |= (1<<j);
if((nxt>>(j+1))&1) nxt ^= (1<<(j+1)),nxt |= (1<<m);
LL gx = f[now][S]+D[i-1][j]+ext;
if(f[now^1][nxt] > gx || (f[now^1][nxt] == gx && g[now^1][nxt] < g[now][S]+1)){
f[now^1][nxt] = gx;g[now^1][nxt] = g[now][S]+1;
}
}
// 横着的边
if(j != 0 && !((S>>j)&1) && !((S>>(j-1))&1)){
int nxt = S;nxt |= (1<<j);nxt |= (1<<(j-1));
if((nxt>>m)&1) nxt ^= (1<<m);
if((nxt>>(j+1))&1) nxt ^= (1<<(j+1)),nxt |= (1<<m);
LL gx = f[now][S]+R[i][j-1]+ext;
if(f[now^1][nxt] > gx || (f[now^1][nxt] == gx && g[now^1][nxt] < g[now][S]+1)){
f[now^1][nxt] = gx;g[now^1][nxt] = g[now][S]+1;
}
}
// 啥都不用
int nxt = S;
if((nxt>>m)&1) nxt ^= (1<<m);
if((nxt>>(j+1))&1) nxt ^= (1<<(j+1)),nxt |= (1<<m);
LL gx = f[now][S];
if(f[now^1][nxt] > gx || (f[now^1][nxt] == gx && g[now^1][nxt] < g[now][S])){
f[now^1][nxt] = gx;g[now^1][nxt] = g[now][S];
}
}
now ^= 1;
}
CLR(f[now^1],0x3f);CLR(g[now^1],0);
FOR(S,0,(1<<(m+1))-1){
int nxt = S;if((nxt>>m)&1) nxt ^= (1<<m);
if(nxt&1) nxt--,nxt |= (1<<m);
LL gx = f[now][S];
if(f[now^1][nxt] > gx || (f[now^1][nxt] == gx && g[now^1][nxt] < g[now][S])){
f[now^1][nxt] = gx;g[now^1][nxt] = g[now][S];
}
}
now ^= 1;
}
LL mn = inf;int ps = -1;
FOR(S,0,(1<<(m+1))-1){
if(mn > f[now][S] || (mn == f[now][S] && ps < g[now][S])){
mn = f[now][S];ps = g[now][S];
}
}
return ps;
}
inline void Solve(){
read(n);read(m);read(k);
FOR(i,0,n-2) FOR(j,0,m-1) read(D[i][j]);
FOR(i,0,n-1) FOR(j,0,m-2) read(R[i][j]);
LL l = -1e14,r = 0,ans = 0;
while(l <= r){
LL mid = (l + r) >> 1;
if(chk(mid) >= k) ans = mid,l = mid+1;
else r = mid-1;
}
chk(ans);
LL mn = inf;int ps = -1;
FOR(S,0,(1<<(m+1))-1){
if(mn > f[now][S]){
mn = f[now][S];ps = g[now][S];
}
}
printf("%lld
",mn-k*ans);
}
int main(){
int T;read(T);
while(T--) Solve();
return 0;
}
[collapse status="false" title="写完了再看"]这题可能是个毒瘤卡常题+轮廓线题 所以要留下充裕的时间写[/collapse]