bzoj3571: [Hnoi2014]画框

题目链接

bzoj3571

题目描述

Description

小T准备在家里摆放几幅画，为此他买来了N幅画和N个画框。为了体现他的品味，小T希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。对于第 幅画与第 个画框的配对，小T都给出了这个配对的平凡度Aij 与违和度Bij 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第i幅画与第Pi个画框配对，则总体不和谐度为

小T希望知道通过搭配能得到的最小的总体不和谐度是多少。

Input

输入文件第 行是一个正整数T ，表示数据组数，接下来是T组数据。
对于每组数据，第 行是一个正整数N，表示有N对画和画框。
第2到第N+1行，每行有N个非负整数，第i+1 行第j个数表示Aij 。
第N+2到第2*N+1行，每行有N个非负整数，第i+N+1 行第j个数表示Bij 。

Output

包含T行，每行一个整数，表示最小的总体不和谐度

Sample Input

1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3

Sample Output

30

HINT

第1幅画搭配第3个画框，第2幅画搭配第1个画框，第3 幅画搭配第2个画框，则总体不和谐度为30
N<=70,T<=3,Aij<=200,Bij<=200

题解

我们将每个方案看成平面上的一个点$(\sum_{i=1}^nA_{i,P_i},\sum_{i=1}^nB_{i,P_i})$ 设横坐标为x，纵坐标为y，x*y=k。那么这是条双曲线，我们要最小化k，就是希望这条双曲线最接近坐标轴。满足要求的点一定在一个下凸壳上，考虑分治：
1.找到平面上y最大和x最大的点（可以用KM算法），将他们连线。
2.找到距离此直线最远的点。与左右的点分别递归下去。怎么找这个点？只要那个点与这两个点构成的三角形面积最大即可。用叉积判断。
$S=(b.x-a.x,b.y-a.y)*(c.x-a.x,c.y-a.y)$
$=(b.x-a.x)*(c.y-a.y)-(b.x-a.y)*(c.x-a.x)$
$=(a.y-b.y)c.x+(b.x-a.x)c.y+(a.x-b.x)*a.y+(b.y-a.y)a.x$
注意到 $(a.x-b.x)*a.y+(b.y-a.y)a.x$ 是常数，我们只要最大化$(a.y-b.y)c.x+(b.x-a.x)c.y$。用$(a.y-b.y)*A_{i,j}+(b.x-a.x)*B_{i,j}$ 当边权跑一遍KM就可以了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;

#define N 80
typedef pair<int,int>P;
P l,r;
int tx[N],ty[N],a[N][N],b[N][N],d[N][N],match[N],n,fix,T;
bool vx[N],vy[N];

bool find(int x){
    vx[x]=true;
    for(int y=1;y<=n;y++)
    if(!vy[y]){
        int tmp=tx[x]+ty[y]-d[x][y];
        if(!tmp) {
            vy[y]=true;
            if(!match[y]||find(match[y])){
                match[y]=x;
                return true;
            }
        } else fix=min(fix,tmp);
    }
    return false;
}
P km(){
    memset(tx,192,sizeof(int)*(n+1));
    memset(ty,0,sizeof(int)*(n+1));
    memset(match,0,sizeof(int)*(n+1));
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++) tx[i]=max(tx[i],d[i][j]);
    for(int x=1;x<=n;x++){
        while(true){
            memset(vy,false,sizeof(bool)*(n+1));
            memset(vx,false,sizeof(bool)*(n+1));
            fix=1000000007;
            if(find(x)) break;
            for(int i=1;i<=n;i++){
                if(vx[i]) tx[i]-=fix;
                if(vy[i]) ty[i]+=fix;
            }
        }
    }
    P ans(0,0);
    for(int i=1;i<=n;i++) ans.first+=a[match[i]][i],ans.second+=b[match[i]][i];
    return ans;
}
int solve(P l,P r){
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++) d[i][j]=a[i][j]*(r.second-l.second)+b[i][j]*(l.first-r.first);
    P mid=km();
    if(mid==l||mid==r) return min(l.first*l.second,r.first*r.second);
    return min(solve(l,mid),solve(mid,r));
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
        for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++) scanf("%d",&b[i][j]);
        for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++) d[i][j]=-a[i][j];
        l=km();
        for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++) d[i][j]=-b[i][j];
        r=km();
        printf("%d\n",solve(l,r));
    }
    return 0;
}