Luogu P3236 [HNOI2014] Picture frame Answer key

Topic link ：P3236 [HNOI2014] Picture frame

The question ： Small T I'm going to put some pictures at home , For this reason, he bought $N$ Painting and $N$ A picture frame . To reflect his taste , Small T I hope I can reasonably match the picture and frame , Make it neither too mediocre nor too contrary .

For the first $i$ The painting is similar to $j$ Pairing of picture frames , Small T Both give the triviality of this pairing $A_{i,j}$ And disobedience $B_{i,j}$. The sum of the total matching degree of each picture frame and the non-uniformity of the whole picture frame is the product of the total matching degree of each picture frame and the non-uniformity of the whole picture frame . say concretely , Set... In the matching scheme $i$ The painting is similar to $P_i$ Frame pairing , The overall disharmony is
$$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{y}=\sum _{i=1}^N{A}_{i,p_i}\times \sum _{i=1}^N{B}_{i,p_i}$$
Small T I hope to know the minimum overall disharmony that can be obtained through collocation .

q779 In water article

This question and P5540 [BalkanOI2011] timeismoney | Minimum product spanning tree It's almost a problem

You can read this first Answer key （

The change is not great , It's basically changing the adjacency matrix

It's just that the algorithm is changed to KM Find the maximum weight perfect match of complete bipartite graph

The time complexity is about $O(k{n}^4)$ about ,$k$ Is a small constant

It's hard to empty , Burst two lines of tears ！！！！

Just as an aside ,dfs The version seems to be $O(n^4)$ Of , It is recommended not to write

The code is as follows

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(75)
int n,g[N][N],a[N][N],b[N][N],Q;
struct vct
{
    
    int x,y;
}ans;
int slack[N],lx[N],ly[N],px[N],py[N],pre[N],d,vx[N],vy[N];
vct operator-(vct a,vct b){
    return (vct){
    a.x-b.x,a.y-b.y};}
int cross(vct a,vct b){
    return a.x*b.y-a.y*b.x;}
void aug(int v)
{
    
    int t;
    while(v)
    {
    
        t=px[pre[v]];
        px[pre[v]]=v;
        py[v]=pre[v];
        v=t;
    }
}
queue<int> q;
void bfs(int s)
{
    
    for(int i=1; i<=n; i++)
        slack[i]=INF,vx[i]=vy[i]=0;
    while(!q.empty())q.pop();
    q.push(s);
    while(1)
    {
    
        while(!q.empty())
        {
    
            int u=q.front();q.pop();
            vx[u]=1;
            for(int i=1; i<=n; i++)
            {
    
                if(!vy[i]&&lx[u]+ly[i]-g[u][i]<slack[i])
                {
    
                    slack[i]=lx[u]+ly[i]-g[u][i];
                    pre[i]=u;
                    if(!slack[i])
                    {
    
                        vy[i]=1;
                        if(!py[i]){
    aug(i);return;}
                        else q.push(py[i]);
                    }
                }
            }
        }
        int d=INF;
        for(int i=1; i<=n; i++)
            if(!vy[i])d=min(d,slack[i]);
        for(int i=1; i<=n; i++)
        {
    
            if(vx[i])lx[i]-=d;
            if(vy[i])ly[i]+=d;
            else slack[i]-=d;
        }
        for(int i=1; i<=n; i++)
        {
    
            if(!vy[i]&&!slack[i])
            {
    
                vy[i]=1;
                if(!py[i]){
    aug(i);return;}
                else q.push(py[i]);
            }
        }
    }
}
vct KM()
{
    
    vct res={
    0,0};
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            lx[i]=max(lx[i],g[i][j]);
    for(int i=1; i<=n; i++)bfs(i);
    for(int i=1; i<=n; i++)
    {
    
        res.x+=a[py[i]][i];
        res.y+=b[py[i]][i];
    }
    if(res.x*res.y<ans.x*ans.y)ans=res;
    for(int i=1; i<=n; i++)
        px[i]=py[i]=lx[i]=ly[i]=pre[i]=0;
        
    return res;
}
void solve(vct A,vct B)
{
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            g[i][j]=-b[i][j]*(B.x-A.x)-a[i][j]*(A.y-B.y);
    vct C=KM();
    if(cross(B-A,C-A)>=0)return;
    solve(A,C);solve(C,B);
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> Q;
    while(Q--)
    {
    
        cin >> n;
        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];
        for(int i=1; i<=n; i++) 
            for(int j=1; j<=n; j++)
                g[i][j]=-a[i][j];
        vct A=KM();
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                g[i][j]=-b[i][j];
        vct B=KM();
        ans=(A.x*A.y<B.x*B.y)?A:B;
        solve(A,B);
        cout << ans.x*ans.y << endl;
    }
    return 0;
}

Reprint please explain the source