BZOJ3571 [Hnoi2014]画框

题面

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

img

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

题解

​ 如果我们把一个方案的A\sum A,B\sum B分别记为x,y,那么答案是最小化xyx*y

​ 如果我们把这个方案投射到坐标系中,设其点坐标为(x,y)(x,y),则答案是求一个反比例函数,使得其经过某个点,并且其的kk最小。

​ 注意到,这相当于让点(x,y)(x,y)越接近坐标系。

​ 可以理解,我们可行的点都是在下凸包中的。

​ 那么其至少包括两个点,一个是A最小的,一个是B最小的,这个我们可以直接用KM得到。

​ 设A最小的点为A,B最小的点为B,那么如何找其它的点(譬如C)?

​ 在直线AB的靠近原点一侧的使得S三角形ABC最大的C,必然是下凸包的一部分。

​ 因此,我们可以求使得三角形ABC面积最大的一个点。

​ 根据叉积,可以知道

S△ABC = (向量AC)\times (向量AB) = (C.x-A.x,C.y-A.y)\times (B.x-A.x,B.y-A.y)

$ = (C.x-A.x)\times (B.y-A.y)-(C.y-A.y)\times (B.x-A.x)$

=(C.x)×(B.yA.y)A.x×(B.yA.y)C.y×(B.xA.x)+A.y×(B.xA.x)=(C.x)\times (B.y-A.y)-A.x\times (B.y-A.y)-C.y\times (B.x-A.x)+A.y\times (B.x-A.x)

​ 注意到A和B是确定的。

​ 故只需要最大化(C.x)×(B.yA.y)(C.y)×(B.xA.x)(C.x)\times (B.y-A.y) - (C.y)\times (B.x-A.x)即可

​ 于是我们把a[i][j]a[i][j]设置为(x[i][j])×(B.yA.y)y[i][j]×(B.xA.x)(x[i][j]) \times (B.y-A.y) - y[i][j] \times (B.x-A.x)此时跑一遍KM。

​ 即可得到点C。

​ 终止条件是叉积小于0.

一些补充

​ 听说随机点凸包上点的期望是O(ln(n))O(\sqrt{ln(n)}),然后这题有n!n!个点。

​ 一次KM算法复杂度是O(n4)O(n^4),可以优化到O(n3)O(n^3),然后O(n4)O(n^4)的常数也足够小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define gc getchar
#define pc putchar
inline int read(){int x=0,f=1;char c=gc();for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(;c>='0'&&c<='9';c=gc())x=x*10+c-48;return x*f;}
inline void write(int x){if(x < 0) putchar('-'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
inline void writeln(int x){write(x);puts("");}
const int oo = 0x3f3f3f3f;const int inf = oo;
#define x first
#define y second
#define mem(x,v) memset(x,v,sizeof(x))
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define file(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define N 110
int a[N][N],b[N][N];
int g[N][N],n,m,q,lx[N],ly[N],vx[N],vy[N],Link[N],slack[N];
int find(int u){
vx[u]=true;
rep(v,0,n){
if(vy[v])continue;
int tmp=lx[u]+ly[v]-g[u][v];
if(tmp==0){
vy[v]=true;
if(Link[v]==-1||find(Link[v])){
Link[v]=u;
return 1;
}
}else if(tmp<slack[v])slack[v]=tmp;
}
return 0;
}
int ans = inf;
pii KM(){
mem(Link,-1),mem(lx,0xc0),mem(ly,0);
rep(i,0,n)rep(j,0,n)lx[i]=max(lx[i],g[i][j]);
rep(i,0,n){
mem(slack,0x3f);
for(;;){
mem(vx,0),mem(vy,0);
if(find(i))break;
int low=inf;
rep(j,0,n)if(!vy[j])low=min(low,slack[j]);
rep(j,0,n)if(vx[j])lx[j]-=low;
rep(j,0,n)if(vy[j])ly[j]+=low;else slack[j]-=low;
}
}
int A = 0,B = 0;
rep(i,0,n){
A+=a[Link[i]][i];
B+=b[Link[i]][i];
}
if(A*B<ans)ans=A*B;
return make_pair(A,B);
}
#define y1 quiroweuroiqwer
#define y2 jesklfad
#define y3 ajfsdkjlhsafd
int Cross(int x1,int y1,int x2,int y2,int x3,int y3){
return (x1-x3)*(y2-y3)-(x2-x3)*(y1-y3);
}
void solve(pii A,pii B){
rep(i,0,n)rep(j,0,n)g[i][j]=a[i][j]*(B.y-A.y)-b[i][j]*(B.x-A.x);
pii C = KM();
if (Cross(B.x,B.y,C.x,C.y,A.x,A.y)>=0) return ;
solve(A,C);solve(C,B);
}
int main(){
file(frame);
int T = read();
while(T--){
ans=inf;
n = read();
rep(i,0,n)rep(j,0,n)a[i][j]=read();
rep(i,0,n)rep(j,0,n)b[i][j]=read();
rep(i,0,n)rep(j,0,n)g[i][j]=-a[i][j];
pii A=KM();
rep(i,0,n)rep(j,0,n)g[i][j]=-b[i][j];
pii B=KM();
solve(A,B);
printf("%d\n",ans);
}
return 0;
}

感想

​ 数形结合的力量真强大。最小化乘积可以看作是最小化反比例函数的K。

文章目录
  1. 1. 题面
  2. 2. 题解
  3. 3. 感想