【bzoj3751】 Hnoi2014—画框

http://www.lydsy.com/JudgeOnline/problem.php?id=3571 (题目链接)

题意

　　给出一个$2*N$个点的二分图，$N*N$条边，连接$i$和$j$的边有两个权值$A[i][j]$和$B[i][j]$。求$A$的和与$B$的和之积最小是多少。

Solution

　　很经典的一个模型，右转题解→_→：http://blog.csdn.net/thy_asdf/article/details/50382556

　　

　　然而我还不会KM，还学习了一发KM。

细节

　　听说这题卡常。。

代码

// bzoj3571

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define inf (1ll<<30)

#define MOD 1000000007

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100;

int vx[maxn],vy[maxn],lx[maxn],ly[maxn],p[maxn],sla[maxn];

int n,g[maxn][maxn],A[maxn][maxn],B[maxn][maxn];

struct point {int x,y;

	friend bool operator == (point a,point b) {

		return a.x==b.x && a.y==b.y;

	}

}L,R;

int match(int x) {

	vx[x]=1;

	for (int y=1;y<=n;y++) if (!vy[y]) {

			int t=lx[x]+ly[y]-g[x][y];

			if (!t) {

				vy[y]=1;

				if (!p[y] || match(p[y])) {p[y]=x;return 1;}

			}

			else sla[y]=min(sla[y],t);

		}

	return 0;

}

point KM() {

	memset(lx,0,sizeof(lx));

	memset(ly,0,sizeof(ly));

	memset(p,0,sizeof(p));

	for (int i=1;i<=n;i++)

		for (int j=1;j<=n;j++) lx[i]=max(lx[i],g[i][j]);

	for (int x=1;x<=n;x++) {

		memset(sla,0x7f,sizeof(sla));

		while (1) {

			memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));

			if (match(x)) break;

			int d=inf;

			for (int i=1;i<=n;i++) if (!vy[i]) d=min(d,sla[i]);

			for (int i=1;i<=n;i++) {

				if (vx[i]) lx[i]-=d;

				if (vy[i]) ly[i]+=d;

			}

		}

	}

	point ans=(point){0,0};

	for (int i=1;i<=n;i++) ans.x+=A[p[i]][i],ans.y+=B[p[i]][i];

	return ans;

}

int solve(point l,point r) {

	for (int i=1;i<=n;i++)

		for (int j=1;j<=n;j++) g[i][j]=A[i][j]*(r.y-l.y)+B[i][j]*(l.x-r.x);

	point mid=KM();

	if (l==mid || r==mid) return min(l.x*l.y,r.x*r.y);

	return min(solve(l,mid),solve(mid,r));

}

int main() {

	int T;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++) g[i][j]=-A[i][j];

		L=KM();

		for (int i=1;i<=n;i++)

			for (int j=1;j<=n;j++) g[i][j]=-B[i][j];

		R=KM();

		printf("%d\n",solve(L,R));

	}

	return 0;

}