bzoj3571————2016——3——12(最小乘积匹配)

bzoj3571

传送门http://www.lydsy.com/JudgeOnline/problem.php?id=3571

题解:

——————来自伟大的thy大神  http://blog.csdn.net/thy_asdf/article/details/50382556

思路:首先看到题目的这个形式,就可以想到最小乘积生成树

这题就是要求最小乘积匹配。

对于这一类问题,我们都可以把每种方案的x之和与y之和作为它的坐标(x,y)

要让乘积最小,那么可能的方案的坐标一定在一个下凸壳上。

首先我们求出x最小的方案的坐标,再求出y最小方案的坐标

这就是凸壳的两个端点A,B。

然后考虑分治,每次找出离直线AB最远的点C,再继续处理

要使距离最远,就是使向量AB和向量AC的叉积最大

即最大化(c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x)

即c.x*(b.y-a.y)+c.y*(a.x-b.x)       -a.x*(b.y-a.y)+a.y*(b.x-a.x)

后面的一部分是常数,不用管。

就是要使c.x*(b.y-a.y)+c.y*(a.x-b.x) 最大化

那么把A[i][j]*(b.y-a.y)+B[i][j]*(a.x-b.x) 做i匹配j的边权

跑一遍KM求出最大匹配即可得出叉积最大的匹配

对于其他的最小乘积XXX,就类似地每次跑一遍XXX的算法求出离AB最远的方案即可

直到不可以继续细分下去就返回两端点的匹配较小的一个即可

虽然可以通过把所有方案构造在凸壳上卡掉这个算法,但随机情况下还是很快的

顺带复习一下KM算法。

KM算法使用来求完备匹配时的最大权匹配,就是所有的x都匹配到一个y,所有y都匹配到一个x

每个点都有一个顶标lx[i],ly[i],设ij匹配的权值为g[i][j]

那么要一直满足任意的一组顶标lx[i]+ly[j]>=g[i][j]

把所有lx[i]+ly[j]==g[i][j]的边拿出来之后的图,如果有完备匹配

那这个完备匹配就一定是最大权匹配。

简单理解就是这个匹配的权值此时一定是所有顶标的和

对于有不在新图中的边(a,b)的另一个匹配

因为g[a][b]<lx[a]+ly[b],所以这个匹配的权值要更小。

lx[i]初值设为max(g[i][j]),ly[i]初值设为0,就满足顶标的条件

然后我们要修改顶标权值,使之在满足条件的前提下,让更多的边进入新图中,才有可能得到一个完备匹配

把所有在当前新图中的匹配中的x的顶标lx[x]减去d,把所有在当前新图中的匹配中的y的顶标加上d

但我们还要满足lx[i]+ly[j]>=g[i][j]

所以d应该取不在当前匹配的y中的min(lx[x]+ly[y]-g[x][y])(x与y有边),这才可以使改变d后的图满足lx[i]+ly[j]>=g[i][j]

那么为什么这样会有新边增加?

对于边(x,y)

1.x,y都在当前匹配lx[x]-=d,ly[y]+=d和不变,原来在新图中,现在还在新图中;

2.x在,y不在,lx[x]-=d,ly[y]不变,原来不在新图中,现在和减小了,可能出现在新图中;

3.x不在,y在,lx[x]不变,ly[y]+=d,原来不在新图中,现在和变大了,不会进入新图中;

4.xy都不在,那么lx[x],ly[y]都不变,原来不在新图中,现在也不在新图中。

所以只有2会产生新边,不会有边消失,那么新图的边数会越来越大,直到找到一个完备匹配。

代码:

#include<iostream>

#include<cstring>
#include<cstdio>
#define inf 0x7fffffff
struct poi{int x,y;}le,ri;
int lx[],ly[],sla[];
int g[][],a[][],b[][],f[];
int n;
bool vx[],vy[];
bool operator ==(poi a,poi b){return a.x==b.x&&a.y==b.y;}
using namespace std;
bool dfs(int x)
{
vx[x]=true;
for (int y=; y<=n; y++)
{
if (!vy[y])
{
int t=lx[x]+ly[y]-g[x][y];
if (!t)
{
vy[y]=true;
if (!f[y]||dfs(f[y]))
{
f[y]=x;
return true;
}
}
else sla[y]=min(sla[y],t);
}
}
return false;
}
poi km()
{
memset(lx,,sizeof(lx)); memset(ly,,sizeof(ly)); memset(f,,sizeof(f));
for (int i=; i<=n; i++) for (int j=; j<=n; j++) lx[i]=max(lx[i],g[i][j]);
for (int x=; x<=n; x++)
{
memset(sla,,sizeof(sla));
while (true)
{
memset(vx,,sizeof(vx)); memset(vy,,sizeof(vy));
if (dfs(x)) break;
int d=inf;
for (int i=; i<=n; i++) if (!vy[i]) d=min(d,sla[i]);
for (int i=; i<=n; i++)
{
if (vx[i]) lx[i]-=d;
if (vy[i]) ly[i]+=d;
}
}
}
poi ans=(poi) {,};
for (int i=; i<=n; i++) ans.x+=a[f[i]][i], ans.y+=b[f[i]][i];
return ans;
}
int slove(poi l,poi r)
{
for(int i=; i<=n; i++) for (int j=; j<=n; j++) g[i][j]=a[i][j]*(r.y-l.y)+b[i][j]*(l.x-r.x);
poi mid=km();
if (l==mid||r==mid) return min(l.x*l.y,r.x*r.y);
else
return min(slove(l,mid),slove(mid,r));
}
int main()
{
int t;
scanf("%d",&t);
for (int z=; z<=t; z++)
{
scanf("%d",&n);
for (int i=; i<=n; i++) for (int j=; j<=n; j++) scanf("%d",&a[i][j]);
for (int i=; i<=n; i++) for (int j=; j<=n; j++) scanf("%d",&b[i][j]);
for (int i=; i<=n; i++) for (int j=; j<=n; j++) g[i][j]=-a[i][j];le=km();
for (int i=; i<=n; i++) for (int j=; j<=n; j++) g[i][j]=-b[i][j];ri=km();
printf("%d\n",slove(le,ri));
}
}

 

这样是O(n^4)的,所以有一个优化,记录一个slack数组 slack[y]=min(lx[x]+ly[y]-g[x][y])(x与y有边)

每次求d就只要对不在匹配中的y的slack取min即可

上一篇:[LeetCode] Number of Lines To Write String 写字符串需要的行数


下一篇:Python实战之Selenium自动化测试web登录