题目大意

给两个n*n的矩阵A,B,求一个排列P,使得最小

需要最小化的式子看起来和最小乘积生成树的非常像啊。

对于一个排列,我们把它抽象成一个平面上的点

这样一个方案的值就是以原点到这个点的连线为对角线的矩形面积。我们要最小化矩形面积。

然后答案只可能在这些点组成的下凸壳中。
于是我们先令边权为A[i,j],做最小匹配,确定出最左边的点L,同理确定出最下边的点R。这两个点肯定都在凸壳上面。然后我们再找出离LR最远的点(往原点方向)Mid,递归下去做L,MID以及MID,R。

有一点要注意的是求最远的点不一定要真的求出每个点到直线的距离,可以用叉积代替,然后求最大匹配就好了。

复杂度:据说n个点的凸包的期望点数是的,于是点数就不会很多啦~

据说这题会卡费用流。。。于是就学了一下KM。。。然后发现网上大部分都是的。。。(然后还自称是,其实不过就是快一倍罢了)当然我也是打的。能过就好~~~

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 79;
struct node
{
    int x,y;
    node(const int _x = 0,const int _y = 0):
        x(_x),y(_y){}
}p[N][N];
void print(const node &a){printf("%d %d\n",a.x,a.y);}
inline bool operator==(const node &lhs,const node &rhs)
{
    return lhs.x == rhs.x && lhs.y == rhs.y;
}
inline int cpr(const node &a,const node &b,const node &c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int w[N][N],mate[N],lx[N],ly[N],visx[N],visy[N],Time,n;
bool dfs(int u)
{
    visx[u] = Time;
    for (int v = 1; v <= n; ++v)
        if (visy[v] != Time && w[u][v] == lx[u] + ly[v]) {
            visy[v] = Time;
            if (!mate[v] || dfs(mate[v]))
                return mate[v] = u,true;
        }
    return false;
}
void update()
{
    int d = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i)
        if (visx[i] == Time)
            for (int j = 1; j <= n; ++j)
                if (visy[j] != Time)
                    d = std::min(d,lx[i] + ly[j] - w[i][j]);
    for (int i = 1; i <= n; ++i) {
        if (visx[i] == Time) lx[i] -= d;
        if (visy[i] == Time) ly[i] += d;
    }
}
node KM()
{
    memset(ly,0,sizeof ly); memset(mate,0,sizeof mate);
    memset(lx,0xC0,sizeof lx);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            lx[i] = std::max(lx[i],w[i][j]);
    for (int i = 1; i <= n; ++i)
        while (1) {
            ++Time;
            if (dfs(i)) break;
            update();
        }
    int res1 = 0,res2 = 0;
    for (int i = 1; i <= n; ++i)
        res1 += p[mate[i]][i].x,res2 += p[mate[i]][i].y;
    return node(res1,res2);
}
int solve(const node &l,const node &r)
{
    int res = std::min(l.x * l.y,r.x * r.y);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            w[i][j] = cpr(p[i][j],r,l);
    node mid = KM();
    print(mid);
    if (mid == l || mid == r) return res;
    return std::min(std::min(solve(l,mid),solve(mid,r)),res);
}
int main()
{
    #ifndef ONLINE_JUDGE
 freopen("3571.in","r",stdin);
    freopen("3571.out","w",stdout);
    #endif
 int T = 0;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d",&p[i][j].x);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d",&p[i][j].y);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                w[i][j] = -p[i][j].x;
        node s = KM();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                w[i][j] = -p[i][j].y;
        node t = KM();
        print(s); print(t);
        printf("%d\n",solve(s,t));
    }
}

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project