题目链接

题目大意

$n \times 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 很难调（对我来说），所以我说下我的错误：

1. 边界情况 特别是在换行的时候 因为我是把多出来的放在最后一位 换行的时候需要操作一下
2. 不要漏掉边 我一开始写的程序漏掉了最上面的边
3. 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\n",mn-k*ans);
}

int main(){
    int T;read(T);
    while(T--) Solve();
    return 0;
}