[BZOJ 3571] 画框

Link：

BZOJ 3571 传送门

Solution：

和 BZOJ2395 的建模完全相同，（BZOJ2395 题解传送门）

仅仅是将其中的基础问题由最小生成树改成了二分图最大完美匹配

只要将原来的Kruscal模块改为KM算法即可

Code：

//by NewErA

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=<<;

struct Vector

{

    int x,y;

    Vector(const int &A,const int &B){x=A,y=B;}Vector(){}

};

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

int Cross(const Vector &a,const Vector &b){return a.x*b.y-a.y*b.x;}

const int MAXN=;

int T,n,G[MAXN][MAXN],dat1[MAXN][MAXN],dat2[MAXN][MAXN];

Vector mina,minb,ans;

ll res;

int match[MAXN*],slack[MAXN*],lx[MAXN],ly[MAXN];

bool visx[MAXN],visy[MAXN];

bool dfs(int u)

{

    visx[u]=true;

    for(int i=;i<=n;i++)

    {

        if(visy[i]) continue;

        int d=lx[u]+ly[i]-G[u][i];

        if(!d)

        {

            visy[i]=true;

            if(match[i]==- || dfs(match[i]))

            {

                match[i]=u;

                return true;

            }

        }

        else slack[i]=min(d,slack[i]);

    }

    return false;

}

Vector KM()  //$O(n^3)$的KM做法

{

    memset(match,-,sizeof(match));

    fill(lx,lx+MAXN,-INF);memset(ly,,sizeof(ly));

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            lx[i]=max(lx[i],G[i][j]);

    for(int i=;i<=n;i++)

    {

        fill(slack,slack+MAXN,INF);

        while(true)

        {

            memset(visx,,sizeof(visx));

            memset(visy,,sizeof(visy));

            if(dfs(i)) break;

            else

            {

                int d=INF;

                for(int i=;i<=n;i++)

                    if(!visy[i]) d=min(d,slack[i]);

                for(int i=;i<=n;i++)

                {

                    if(visx[i]) lx[i]-=d;

                    if(visy[i]) ly[i]+=d;

                    else slack[i]-=d;

                }

            }

        }

    }

    Vector cur=Vector(,);

    for(int i=;i<=n;i++)

        cur.x+=dat1[match[i]][i],cur.y+=dat2[match[i]][i];

    if(res>(ll)cur.x*(ll)cur.y) res=(ll)cur.x*(ll)cur.y; //注意开long long

    return cur;

}

void Solve(Vector A,Vector B)

{

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            G[i][j]=-(dat1[i][j]*(A.y-B.y)+dat2[i][j]*(B.x-A.x)); //修改权值

    Vector C=KM();

    if(Cross(B-A,C-A)>=) return;

    Solve(A,C);Solve(C,B);

}

int main()

{

    cin >> T;

    while(T--)

    {

        cin >> n;res=*;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                cin >> dat1[i][j],G[i][j]=-dat1[i][j]; //最小匹配转为最大匹配，权值由正变为负即可

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                cin >> dat2[i][j];

        mina=KM();

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                G[i][j]=-dat2[i][j];

        minb=KM();

        Solve(mina,minb);

        cout << res << endl;

    }

    return ;

}

Review：

1、需要注意的就是最小匹配转为最大匹配的手法：

将原来的正权值求最小变为负权值求最大

2、千万不能再忘开long long 了！