BZOJ 3571: [Hnoi2014]画框

3571: [Hnoi2014]画框

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 996 Solved: 561
[Submit][Status][Discuss]

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

HINT

第1幅画搭配第3个画框，第2幅画搭配第1个画框，第3 幅画搭配第2个画框，则总体不和谐度为30

N<=70,T<=3,Aij<=200,Bij<=200

Source

分析：

看起来很眼熟的样子...

奥...最小乘积生成树...

题解戳这里~~~

我们就把$kruskal$的过程换成最大权匹配用$KM$算法求一求就好啦...

如果不会$KM$算法，请自行到百度百科学习~~~

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define inf 0x3f3f3f3f
using namespace std;

const int maxn=70+5;

int lx[maxn],ly[maxn],pre[maxn],visx[maxn],visy[maxn];
int n,sum,cas,lack,a[maxn][maxn],b[maxn][maxn],w[maxn][maxn];

struct M{
	int x,y;
	M(int X=0,int Y=0){
		x=X,y=Y;
	}
};

inline bool find(int x){
	visx[x]=1;
	for(int y=1;y<=n;y++)
		if(!visy[y]){
			int tmp=lx[x]+ly[y]-w[x][y];
			if(!tmp){
				visy[y]=1;
				if(pre[y]==-1||find(pre[y]))
					return pre[y]=x,true;
			}
			else lack=min(lack,tmp);
		}
	return false;
}

inline M KM(void){
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	memset(pre,-1,sizeof(pre));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			lx[i]=max(lx[i],w[i][j]);
	for(int x=1;x<=n;x++)
		while(12){
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			lack=inf;
			if(find(x)) break;
			for(int i=1;i<=n;i++){
				if(visx[i]) lx[i]-=lack;
				if(visy[i]) ly[i]+=lack;
			}
		}
	M res;
	for(int i=1;i<=n;i++)
		res.x+=a[pre[i]][i],res.y+=b[pre[i]][i];
	sum=min(sum,res.x*res.y);
	return res;
}

inline void solve(M A,M B){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			w[i][j]=-b[i][j]*(B.x-A.x)-a[i][j]*(A.y-B.y);
	M C=KM();
	if((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x)>=0) return;
	solve(A,C);solve(C,B);
}

signed main(void){
#ifndef ONLINE_JUDGE	
	freopen("in.txt","r",stdin);
#endif
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n);sum=inf;
		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++)
				w[i][j]=-a[i][j];
		M A=KM();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				w[i][j]=-b[i][j];
		M B=KM();
		solve(A,B);
		printf("%d
",sum);
	}
	return 0;
}

By NeighThorn