洛谷P3236 [HNOI2014]画框题解

题目链接：P3236 [HNOI2014]画框

题意：小 T 准备在家里摆放几幅画，为此他买来了 $N$ 幅画和 $N$ 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。

对于第 $i$ 幅画与第 $j$ 个画框的配对，小 T 都给出了这个配对的平凡度 $A_{i, j}$ 与违和度 $B_{i, j}$ 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第 $i$ 幅画与第 $P_i$ 个画框配对，则总体不和谐度为
$\mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i}$
小 T 希望知道通过搭配能得到的最小的总体不和谐度是多少。

~~q779在水文章~~ $🐒$

这道题和P5540 [BalkanOI2011] timeismoney | 最小乘积生成树几乎就是一道题

可以先看下这篇题解（

变化不是很大，基本上就是改一下邻接矩阵啥的

只不过算法换成了KM求完全二分图最大权完美匹配

时间复杂度大概在 $O(kn^4)$ 左右， $k$ 为一个小常数

多测不清空，爆零两行泪！！！！

说句题外话，dfs版本好像是 $O(n^4)$ 的，建议不要写

代码如下

#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;
}