#2205. 「HNOI2014」画框

最小乘积生成树+KM二分图带权匹配

维护一个\((\sum A,\sum B)\)的匹配下凸包，答案在这些点中产生。

具体的，凸包两端可以直接跑单独的\(A\)权与\(B\)权的最小带权匹配

然后进行分治，每次找离线段的最远点加入匹配

用叉积推一下式子可以得到进行匹配的图的边权，然后继续跑KM就可以了

---

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

#define yuucute 1

const int N=80;

using std::min;

using std::max;

struct Point

{

	int x,y;

	Point(){x=0,y=0;}

	Point(int X,int Y){x=X,y=Y;}

	Point friend operator -(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}

};

int Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}

int va[N],vb[N],w[N][N],a[N][N],b[N][N],mat[N],la[N],lb[N],n,mi,ans;

bool dfs(int now)

{

	va[now]=1;

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

		if(!vb[v])

		{

			if(w[now][v]==la[now]+lb[v])

			{

				vb[v]=1;

				if(!mat[v]||dfs(mat[v]))

					return mat[v]=now,true;

			}

			else mi=min(mi,la[now]+lb[v]-w[now][v]);

		}

	return false;

}

Point KM()

{

	memset(mat,0,sizeof mat);

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

	{

		la[i]=-(1<<30);

		lb[i]=0;

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

			la[i]=max(la[i],w[i][j]);

	}

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

	{

		while(yuucute)

		{

			memset(va,0,sizeof va);

			memset(vb,0,sizeof vb);

			mi=1<<30;

			if(dfs(i)) break;

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

			{

				if(va[j]) la[j]-=mi;

				if(vb[j]) lb[j]+=mi;

			}

		}

	}

	Point ret;

	for(int i=1;i<=n;i++) ret.x+=a[mat[i]][i],ret.y+=b[mat[i]][i];

	return ret;

}

void Divide(Point A,Point B)

{

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

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

			w[i][j]=a[i][j]*(B.y-A.y)-b[i][j]*(B.x-A.x);

	Point C=KM();

	if(Cross(C-A,B-A)<=0) return;

	ans=min(ans,C.x*C.y);

	Divide(A,C),Divide(C,B);

}

void work()

{

	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++)

            w[i][j]=-a[i][j];

	Point A=KM();

	ans=A.x*A.y;

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

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

            w[i][j]=-b[i][j];

	Point B=KM();

	ans=min(ans,B.x*B.y);

	Divide(A,B);

	printf("%d\n",ans);

}

int main()

{

	int T;scanf("%d",&T);

	while(T--) work();

	return 0;

}

---

2019.2.19