题解：P3236 [HNOI2014] 画框

· · 题解

对每种匹配方式，将其看做平面上一点 (\sum A_{i,p_i},\sum B_{i,p_i})，显然答案在点集左下凸包上。

无法直接求出凸包，先分别求出点 A：使 \sum A_{i,p_i} 最小，不管 \sum B。点 B 同理。这两个点一定是左下凸包的两端。

接下来是一个递归算法：求出到直线 AB 左下距离最远的点 C，然后递归做直线 AC,BC。即最小化 \overrightarrow{AB}\times \overrightarrow{AC}=(x_B-x_A)y_C+(y_A-y_B)x_C+y_Bx_A-x_By_A。

即最小化 (y_A-y_B)\sum A_{i,p_i}+(x_B-x_A)\sum B_{i,p_i}。那么将一对匹配权值改为 (y_A-y_B)A_{i,j}+(x_B-x_A)B_{i,j}，做二分图最小权完美匹配即可。

边界条件：若找不到 C（C 不在 AB 左下）则停止。

MCMF 卡常技巧

// C++98
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pr;

#define x first 
#define y second
#define rep(i,a,b) for(int i = (a);i <= (b);++i)

#ifdef ONLINE_JUDGE
static char buf[2097152],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,2097152,stdin),p1==p2)?EOF:*p1++
#endif

inline int read(){
    register int x = 0;
    register char c = getchar();
    for(;c < '0' || c > '9';c = getchar());
    for(;c >= '0' && c <= '9';c = getchar())
        x = x * 10 + (c ^ '0');
    return x;
}

const int N = 145,M = 12005,inf = 0x3f3f3f3f;

int T,n,a[N][N],b[N][N],st,ed,ans;

struct edge{ int v,w,c; } E[M]; int nxt[M];

int Etot = 1,from[N];

void add(int u,int v,int w,int c){
    E[++Etot] = (edge){v,w,c}; nxt[Etot] = from[u]; from[u] = Etot;
    E[++Etot] = (edge){u,0,-c}; nxt[Etot] = from[v]; from[v] = Etot;
}

int Q[N * 5],pnt[N];
int dis[N],now[N]; bool vis[N];

int SPFA(){
    int L = N,R = N - 1; Q[++R] = st;
    for(int i = 0;i <= ed;++i) dis[i] = inf;
    dis[st] = 0;
    while(L <= R){
        int u = Q[L++];
        vis[u] = 0;
        for(int i = now[u] = from[u];i;i = nxt[i]){
            int v = E[i].v,w = E[i].w,c = E[i].c;
            if(w && dis[v] > dis[u] + c){
                dis[v] = dis[u] + c;
                if(!vis[v]){
                    vis[v] = 1;
                    if(L > R || dis[v] > dis[Q[L]]) Q[++R] = v;
                    else Q[--L] = v;
                }
            }
        }
    }
    return dis[ed] < inf;
}

int dfs(int u,int fl){
    if(u == ed) return fl;
    vis[u] = 1;
    int v,k,cnt = 0;
    for(int i = now[u];i;i = nxt[i]){
        now[u] = i;
        v = E[i].v;
        if(E[i].w > 0 && dis[v] == dis[u] + E[i].c && !vis[v]){
            k = dfs(v,min(fl,E[i].w));
            if(u <= n && k) pnt[u] = v - n;
            E[i].w -= k,E[i ^ 1].w += k;
            cnt += k,fl -= k;
            if(!fl) break;
            if(!k) dis[v] = -1;
        }
    }
    vis[u] = 0;
    return cnt;
}

pr mcmf(int x,int y){
    int k = 0;
    rep(i,1,n) rep(j,1,n) k += 2,E[k].c = x * a[i][j] + y * b[i][j],E[k ^ 1].c = -E[k].c;
    while(SPFA()) dfs(st,inf);
    int sa = 0,sb = 0;
    rep(i,1,n){
        sa += a[i][pnt[i]],sb += b[i][pnt[i]];
        int k = ((i - 1) * n + pnt[i]) * 2;
        E[k].w = 1,E[k ^ 1].w = 0;
    }
    rep(i,1,2 * n) k += 2,E[k].w = 1,E[k ^ 1].w = 0;
    ans = min(ans,sa * sb);
    return pr(sa,sb);
}

pr operator-(const pr &a,const pr& b){ return pr(a.x - b.x,a.y - b.y); } 

int cross(pr a,pr b){ return a.x * b.y - a.y * b.x; }

void sol(pr a,pr b){
    pr c = mcmf(a.y - b.y,b.x - a.x);
    if(cross(b - a,c - a) < 0) sol(a,c),sol(c,b);
} 

int main(){
    for(T = read();T--;){
        n = read(),ed = 2 * n + 1,ans = 1e9;
        rep(i,1,n) rep(j,1,n) add(i,j + n,1,a[i][j] = read());
        rep(i,1,n) rep(j,1,n) b[i][j] = read();
        rep(i,1,n) add(st,i,1,0),add(i + n,ed,1,0);
        pr a = mcmf(1,0);
        pr b = mcmf(0,1);
        sol(a,b);
        printf("%d\n",ans);
        Etot = 1;
        for(int i = 0;i <= ed;++i) from[i] = 0;
    }
    return 0;
}