常数好一点的话费用流可以跑过。

Solution

https://www.luogu.org/problemnew/solution/P3236
https://blog.csdn.net/zmh964685331/article/details/50859054

LOJ 时限不对过不去。

Code

// Code by ajcxsu
// Problem: frame2

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;

const int N=150, M=2e4+10, D=70, s=N-1, t=N-2;
int h[N], to[M], V[M], nexp[M], p=2, bp;
bitset<M> W, BW;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
#define sins(a, b) ins(a, b), ins(b, a)

int a[N][N], b[N][N], g[N][N];
int n;
void build(int k1, int k2) {
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) g[i][j]=k1*a[i][j]+k2*b[i][j];
}
struct Node { int x, y; } ;
Node operator - (Node a, Node b) { return {a.x-b.x, a.y-b.y}; }
int operator * (Node a, Node b) { return a.x*b.y-a.y*b.x; }
int dist[N], pre[N], preu[N]; bool S[N];
queue<int> qu;
int cnt;
double tot;
clock_t cs;
bool spfa() {
    CLR(dist, 0x3f), CLR(pre, 0);
    dist[s]=0;
    qu.push(s);
    int na;
    while(!qu.empty()) {
        na=qu.front(), qu.pop(), S[na]=0;
        for(int u=h[na];u;u=nexp[u])
            if(W[u] && dist[to[u]]>dist[na]+V[u]) {
                dist[to[u]]=dist[na]+V[u], pre[to[u]]=na, preu[to[u]]=u;
                if(!S[to[u]]) qu.push(to[u]), S[to[u]]=1;
            }
    }
    if(!pre[t]) return false;
    na=t;
    while(pre[na]) {
        W[preu[na]]=0, W[preu[na]^1]=1;
        na=pre[na];
    }
    return true;
}
Node solve() {
    W=BW;
    p=bp;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) V[p]=g[i][j], V[p^1]=-g[i][j], p+=2;
    while(spfa());
    Node ret={0, 0};
    for(int i=1;i<=n;i++)
    for(int u=h[i];u;u=nexp[u])
        if(to[u]!=s && !W[u]) ret.x+=a[i][to[u]-D], ret.y+=b[i][to[u]-D];
    return ret;
}

int ans=0x7fffffff;
void dfs(Node A, Node B) {
    build(A.y-B.y, B.x-A.x);
    Node C=solve();
    ans=min(ans, C.x*C.y);
    if((B-A)*(C-A)<0) dfs(A, C), dfs(C, B);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    for(int i=2;i<M;i+=2) BW[i]=1;
    int t;
    cin>>t;
    while(t--) {
        cin>>n;
        p=2, memset(h, 0, sizeof(h));
        for(int i=1;i<=n;i++) sins(s, i), sins(i+D, ::t);
        bp=p;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) sins(i, j+D);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>a[i][j];
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>b[i][j];
        build(1, 0);
        Node L=solve();
        build(0, 1);
        Node R=solve();
        ans=min(L.x*L.y, R.x*R.y);
        dfs(L, R);
        cout<<ans<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3236.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆