洛谷3236 [HNOI2014]画框

Luogu

BZOJ

分析

类似于最小乘积生成树的方法。

把每一种匹配的 $\sum a_i$ 和 $\sum b_i$ 看做二维坐标 $(x,y)$ ,现在要找 $x\cdot y$ 最小的点。

这个东西可以分三步去求:

求出与 $x$ 轴和 $y$ 轴最近的点

非常简单,分别把 $a$ 和 $b$ 作为权值,跑$\texttt{KM}$就行了。

记与 $x$ 轴最近的点为 $A$,与 $y$ 轴最近的点为 $B$。

找到一个在$AB$的左侧且离$AB$最远的点

现在的情况是这样(来自hyj的blog):

img

我们要找点 $C$ 。

事实上, $C$ 就是在 $AB$ 左侧,且使得 $S_{\triangle ABC}$ 最大的点。

我们知道有$S_{\triangle ABC}=\frac{\vec{AB}*\vec{AC}}{2}$。(然而这个面积是负的,所以要让它最小)。

所以就是要最小化 $\vec{AB}*\vec{AC}$ 。

经过一番展开+推导后发现,把匹配的权值 $w[i][j]$ 改为 $(y_A-y_B)a[i][j]+(x_B-x_A)b[i][j]$ ,再跑$\texttt{KM}$即可。

递归处理左右两侧

递归处理 $AC$ 和 $CB$ 即可。

注意当找到的 $C$ 在 $AB$的右侧时为边界,直接返回。


注意,以上所有的$\texttt{KM}$要求的都是最小权匹配

以及,细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=70+10;
const int inf=0x3f3f3f3f;

struct Point { int x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n;
Point ans;

namespace KM {
    int a[N][N],b[N][N],w[N][N];
    int lx[N],ly[N];
    int match[N],s[N],t[N];
    
    inline void build(int wx,int wy) {
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                w[i][j]=-(wx*a[i][j]+wy*b[i][j]);
    }
    
    inline int Hungary(int i) {
        s[i]=1;
        for (re int j=1;j<=n;++j)
            if (lx[i]+ly[j]==w[i][j]&&!t[j]) {
                t[j]=1;
                if (!match[j]||Hungary(match[j])) return match[j]=i;
            }
        return 0;
    }    
    inline void update() {
        int p=inf;
        for (re int i=1;i<=n;++i) {
            if (!s[i]) continue;
            for (re int j=1;j<=n;++j)
                if (!t[j]) p=min(p,lx[i]+ly[j]-w[i][j]);
        }
        for (re int i=1;i<=n;++i) {
            if (s[i]) lx[i]-=p;
            if (t[i]) ly[i]+=p;
        }
    }
    inline Point work() {
        for (re int i=1;i<=n;++i) {
            match[i]=lx[i]=ly[i]=0;
            for (re int j=1;j<=n;++j)
                lx[i]=max(lx[i],w[i][j]);
        }
        for (re int i=1;i<=n;++i) {
            while (233) {
                for (re int j=1;j<=n;++j) s[j]=t[j]=0;
                if (Hungary(i)) break;
                else update();
            }
        }
        Point res=(Point){0,0};
        for (re int i=1;i<=n;++i)
            res.x+=a[match[i]][i],res.y+=b[match[i]][i];
        ll Ans=1ll*ans.x*ans.y,now=1ll*res.x*res.y;
        if (now<Ans) ans=res;
        return res;
    }
}

inline void solve(Point A,Point B) {
    KM::build(A.y-B.y,B.x-A.x);
    Point C=KM::work();
    if (cross(B-A,C-A)>=0) return;
    solve(A,C),solve(C,B);
}

int main() {
    int T=read();
    while (T--) {
        n=read(); ans=(Point){inf,inf};
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                KM::a[i][j]=read();
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                KM::b[i][j]=read();
        KM::build(1,0); Point A=KM::work();
        KM::build(0,1); Point B=KM::work();
        solve(A,B); printf("%d\n",ans.x*ans.y);
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 05 PM

发表评论