科普~KM算法
今天和朋友聊天,聊到了KM,今天Xushine研究院就和大家讨论下KM算法~
先来看看KM的算法描述:
KM算法求的是完备匹配下的最大权匹配: 在一个二分图内,左顶点为X,右顶点为Y,现对于每组左右连接XiYj有权wij,求一种匹配使得所有wij的和最大。
再来看看基本原理~
该算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ],顶点Yj的顶标为B[ j ],顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻,对于任一条边(i,j),A[ i ]+B[j]>=w[i,j]始终成立。
KM算法的正确性基于以下定理:
若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图(称做相等子图)有完备匹配,那么这个完备匹配就是二分图的最大权匹配。
看着KM的算法还是蛮简单的~
但是值得注意的是,这个简单的KM算法在我们的ACM比赛中会经常的用到~
下面我先贴一个模板~
/*其实在求最大 最小的时候只要用一个模板就行了,把边的权值去相反数即可得到另外一个.求结果的时候再去相反数即可*/
/*最大最小有一些地方不同。。*/
#include <iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
//赤裸裸的模板啊。。
const int maxn = 101;
const int INF = (1<<31)-1;
int w[maxn][maxn];
int lx[maxn],ly[maxn]; //顶标
int linky[maxn];
int visx[maxn],visy[maxn];
int slack[maxn];
int nx,ny;
bool find(int x)
{
visx[x] = true;
for(int y = 0; y < ny; y++)
{
if(visy[y])
continue;
int t = lx[x] + ly[y] – w[x][y];
if(t==0)
{
visy[y] = true;
if(linky[y]==-1 || find(linky[y]))
{
linky[y] = x;
return true; //找到增广轨
}
}
else if(slack[y] > t)
slack[y] = t;
}
return false; //没有找到增广轨(说明顶点x没有对应的匹配,与完备匹配(相等子图的完备匹配)不符)
}
int KM() //返回最优匹配的值
{
int i,j;
memset(linky,-1,sizeof(linky));
memset(ly,0,sizeof(ly));
for(i = 0; i < nx; i++)
for(j = 0,lx[i] = -INF; j < ny; j++)
if(w[i][j] > lx[i])
lx[i] = w[i][j];
for(int x = 0; x < nx; x++)
{
for(i = 0; i < ny; i++)
slack[i] = INF;
while(true)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(find(x)) //找到增广轨,退出
break;
int d = INF;
for(i = 0; i < ny; i++) //没找到,对l做调整(这会增加相等子图的边),重新找
{
if(!visy[i] && d > slack[i])
d = slack[i];
}
for(i = 0; i < nx; i++)
{
if(visx[i])
lx[i] -= d;
}
for(i = 0; i < ny; i++)
{
if(visy[i])
ly[i] += d;
else
slack[i] -= d;
}
}
}
int result = 0;
for(i = 0; i < ny; i++)
if(linky[i]>-1)
result += w[linky[i]][i];
return result;
}
int main()
{
// freopen("g:/1.txt","r",stdin);
while(true)
{
scanf("%d%d",&nx,&ny);
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c),a+b+c)
{
w[a][b]=c;
}
printf("%d\\n",KM());
break;
}
return 0;
}
下面我们用一道题目来实现 本题是HUDA的1853~~
题目地址如下:
我们先简单的分析下本道题目:http://acm.hdu.edu.cn/showproblem.php?pid=1853
如果要保证图有环,并且环之间没有交点的话,那么必然每个点的出度和入度都应为1,因此我们可以把一个点拆成两个点,分别表示出度及入度,然后去找拆点后构成的二分图的完美匹配。
AC代码如下:
/*其实在求最大 最小的时候只要用一个模板就行了,把边的权值去相反数即可得到另外一个.求结果的时候再去相反数即可*/
/*最大最小有一些地方不同。。*/
#include <iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
int n,m;
const int maxn = 105;
const int INF = 0xffffff;
int w[maxn][maxn];
int lx[maxn],ly[maxn]; //顶标
int linky[maxn];
int visx[maxn],visy[maxn];
int slack[maxn];
bool find(int x)
{
visx[x] = true;
for(int y = 1; y <=n; y++)
{
if(visy[y])
continue;
int t = lx[x] + ly[y] – w[x][y];
if(t==0)
{
visy[y] = true;
if(linky[y]==-1 || find(linky[y]))
{
linky[y] = x;
return true; //找到增广轨
}
}
else if(slack[y] > t)
slack[y] = t;
}
return false; //没有找到增广轨(说明顶点x没有对应的匹配,与完备匹配(相等子图的完备匹配)不符)
}
int KM() //返回最优匹配的值
{
int i,j;
memset(linky,-1,sizeof(linky));
memset(ly,0,sizeof(ly));
for(i = 1; i <=n; i++)
{
lx[i] = -INF;
for(j = 1; j <=n; j++)
if(w[i][j] > lx[i])
lx[i] = w[i][j];
}
for(int x = 1; x <=n; x++)
{
for(i = 1; i <=n; i++)
slack[i] = INF;
while(true)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(find(x)) //找到增广轨,退出
break;
int d = INF;
for(i = 1; i <=n; i++) //没找到,对l做调整(这会增加相等子图的边),重新找
{
if(!visy[i] && d > slack[i])
d = slack[i];
}
for(i = 1; i <=n; i++)
{
if(visx[i])
lx[i] -= d;
}
for(i = 1; i <=n; i++)
{
if(visy[i])
ly[i] += d;
else
slack[i] -= d;
}
}
}
int result = 0 ;
for(i = 1; i <=n; i++)
{
if(linky[i]==-1||w[linky[i]][i]==-INF)
return 1;
else result += w[linky[i]][i];
}
return result;
}
int main()
{
// freopen("g:/1.txt","r",stdin);
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
w[i][j]=-INF;
}
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(-c>w[a][b])
w[a][b]=-c;
}
printf("%d\\n",-KM());
}
return 0;
}
还以为能抢到沙发。。结果被干掉了。。。
除了YM,大D别的啥都不说了~
+1