BZOJ3571: [Hnoi2014]画框-布布扣-bubuko.com

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

技术分享图片

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

这题目难道掉牙了。。。

我们会发现这个很像最小乘积生成树。

于是我们把一种匹配的$\sum A_i$和$\sum B_i$分别看作横纵坐标，然后找$x \times y$最小的点。

可以先找出$x$最小的点$A$和$y$最小的点$B$，然后找$AB$左下方离$AB$最远的点$C$。

即$\overrightarrow{AB}\times\overrightarrow{AC}$最小。

然后把$\overrightarrow{AB}\times\overrightarrow{AC}$拆开：

$$\left.\begin{array}{}\overrightarrow{AB}\times\overrightarrow{AC}&=&(x_B-x_A)\times(y_C-y_A)-(y_B-y_A)\times(x_C-x_A) \\&=&(x_B-x_A)\times y_C+(y_A-y_B)\times x_C+y_B\times x_A-x_B\times y_A\end{array}\right.$$

在程序中我的$A,B,C$用$one,two,three$代替了，注意一下。。。

那么把权值改成$map[i][j]=(y_A-y_B)\times A[i][j]+(x_B-x_A)\times B[i][j]$，再用带权二分图匹配就可以找出$C$。

带权二分图匹配这个丢给了$KM$，当然费用流也是可行的，不过我比较懒就不写了。。。

找出$C$后用叉积判断$C$是不是在$AB$的下方，如果是，就递归解决线段$AC$和$CB$。

然后就做完了。。。

没想到头一次写$KM$还是在这道题，我连板子题还没写呢。。。

没学会走，先学会飞了。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 80
#define MAX 999999999
using namespace std;
int n,ans;
int A[MAXN][MAXN],B[MAXN][MAXN];
struct Vector{
	int x,y;
	friend Vector operator +(const Vector p,const Vector q){return (Vector){p.x+q.x,p.y+q.x};}
	friend Vector operator -(const Vector p,const Vector q){return (Vector){p.x-q.x,p.y-q.y};}
	friend int operator *(const Vector p,const Vector q){return p.x*q.y-p.y*q.x;}
};
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
namespace G{
	int f[MAXN],valx[MAXN],valy[MAXN],val[MAXN],map[MAXN][MAXN];
	bool visx[MAXN],visy[MAXN];
	inline void buildgraph(int x,int y){
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)map[i][j]=-(x*A[i][j]+y*B[i][j]);
	}
	bool find(int x){
		visx[x]=true;
		for(int i=1;i<=n;i++){
			if(visy[i])continue;
			int t=valx[x]+valy[i]-map[x][i];
			if(!t){
				visy[i]=true;
				if(f[i]==-1||find(f[i])){
					f[i]=x;
					return true;
				}
			}
			else val[i]=min(val[i],t);
		}
		return false;
	}
	Vector KM(){
		Vector s=(Vector){0,0};
		memset(f,-1,sizeof(f));
		memset(valx,0,sizeof(valx));
		memset(valy,0,sizeof(valy));
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)valx[i]=max(valx[i],map[i][j]);
		for(int i=1;i<=n;i++){
			memset(val,63,sizeof(val));
			while(1){
				memset(visx,false,sizeof(visx));
				memset(visy,false,sizeof(visy));
				if(find(i))break;
				int w=MAX;
				for(int i=1;i<=n;i++)if(!visy[i])w=min(w,val[i]);
				for(int i=1;i<=n;i++)if(visx[i])valx[i]-=w;
				for(int i=1;i<=n;i++){
					if(visy[i])valy[i]+=w;
					else val[i]-=w;
				}
			}
		}
		for(int i=1;i<=n;i++){
			s.x+=A[f[i]][i];
			s.y+=B[f[i]][i];
		}
		return s;
	}
}
void solve(Vector one,Vector two){
	G::buildgraph(one.y-two.y,two.x-one.x);
	Vector three=G::KM();
	ans=min(ans,three.x*three.y);
	if(((two-one)*(three-one))>=0)return;
	solve(one,three);solve(three,two);
}
void work(){
	Vector one,two;
	G::buildgraph(1,0);
	one=G::KM();
	G::buildgraph(0,1);
	two=G::KM();
	ans=min(one.x*one.y,two.x*two.y);
	solve(one,two);
	printf("%d\n",ans);
}
void init(){
	n=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)A[i][j]=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)B[i][j]=read();
}
int main(){
	int t=read();
	while(t--){
		init();
		work();
	}
    return 0;
}

BZOJ3571: [Hnoi2014]画框

Description

Input

Output

Sample Input

Sample Output

HINT

题解Here!

在程序中我的$A,B,C$用$one,two,three$代替了，注意一下。。。