首页 > 代码库 > Bipartitegraph2195EM
Bipartitegraph2195EM
EM算法：
该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点 Xi 的顶标为 A[ i ]，顶点 Yj 的顶标为 B[ j ]，顶点 Xi 与 Yj 之间的边权为 w[i,j]。
在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。
初始时为了使 A[ i ]+B[j]>=w[i,j]恒成立，令 A[ i ]为所有与顶点 Xi 关联的边的最大权，B[j]=0。
KM 算法的正确性基于以下定理：
若由二分图中所有满足 A[ i ]+B[j]=w[i,j]的边(i,j)（1.所有边满足 A[ i ]+B[j]=w[i,j]）构成的子图（称做相等子图）有完备匹配（2.是完备匹配），那么这个完备匹配就是二分图的最大权匹配。
首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X 点集中的所有点（X顶点比Y顶点少的时候）都有对应的匹配或者是Y 点集中所有的点（Y顶点比X顶点少的时候）都有对应的匹配，则称该匹配为完备匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它属于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不属于相等子图，那么它的边权和小于所有顶点的顶标和（说明边选取的不是最优的）。所以相等子图的完备匹配一定是二分图的最大权匹配。
我们求当前相等子图的完备匹配失败了，是因为对于某个 X 顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是 X 顶点。现在我们把交错树中 X 顶点的顶标全都减小某个值 d，交错书Y 顶点（只对树里面的进行修改）的顶标全都增加同一个值 d，那么我们会发现：
1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
2）两端都不在交错树中的边(i,j)，A[ i ]和 B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
3）X 端不在交错树中，Y 端在交错树中的边(i,j)，它的 A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
4）X 端在交错树中，Y 端不在交错树中的边(i,j)，它的 A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中 x1->y4 这条边）
现在的问题就是求 d 值了。为了使 A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d 应该等于：
Min{A[i]+B[j]-w[i,j] | Xi 在交错树中，Yi 不在交错树中}。
A’[i]=A[i]-(A[i]]+B[j]-w[i,j])=w[i]-B[j]
B’[j]=B[j]
A’[i]+B’[j]=w[i,j]
另外d为最小的，因此该边是能取到的最大的一个（x需要减D），保证了最优化。
从上面四条可以看到前三条肯定不会出现错误，唯有可能产生错误的是第四条，因为可能 A[ i ]+B[j]减小后，比w[ij]还小，那么就错了。所以，本来应该从所有的边中寻找最小Min{A[i]+B[j]-w[i,j] ，但因为可能出现错误的，只会是第四条，因此从Xi 在交错树中，Yi 不在交错树中寻找。
[KM算法的几种转化]
KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。
KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。
KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出e^a就是最大积匹配。至于精度问题则没有更好的办法了。
给了两个算法，其实后面优化的了 更容易理解
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int MAXN = 110;
const int inf = -0x3ffffff;
int count_h;
struct node
{
int pos_x,pos_y;
int node_num;
node()
{
pos_x=0,pos_y=0;
node_num=0;
}
};
int bin_map[MAXN][MAXN];
char ch[MAXN][MAXN];
bool vis_x[MAXN],vis_y[MAXN];
int lx[MAXN],ly[MAXN];
int result[MAXN];
bool find(int a,int n)//判断第a能否找到房子
{
vis_x[a] = true;//直接假设首次访问的节点已经加入相等子图
for(int i=1;i!=n;i++)
{
if(!vis_y[i]&&bin_map[a][i]==lx[a]+ly[i])//bin_map[a][i]==lx[a]+ly[i]即为相等子图的条件
{
vis_y[i] = true;//y集合中满足相等子图的i都被标记
if(result[i]==-1||find(result[i],n))
{
result[i] = a;
return true;
}
}
}
return false;
}
int best_match(int n)//开始匹配
{
memset(ly,0,sizeof(ly));//y标值为0
for(int i=1;i!=n;i++)
{
lx[i] = inf;
for(int j=1;j!=n;j++)//这里的题目 人和房子数目是一样的
{
if(lx[i]<bin_map[i][j])
lx[i] = bin_map[i][j];//X的标值为最大的那个
}
}
memset(result,-1,sizeof(result));
for(int u=1;u!=n;u++)
{
while(1)
{
memset(vis_x,false,sizeof(vis_x));//将前面的x集合中相等子图的节点标记为不在里面。
memset(vis_y,false,sizeof(vis_y));
if(find(u,n))//找到了，才继续下一个u。如果找不到更新lx[],ly[]后仍然在while(1)中没有出来,FIND函数之后，标记的VIST[X]是指本来就在相等子图里面的，标记的VISIT[Y]是指原先在相等子图的。但是，可能存在部分本来在相等子图 却没有标记的情况（标记必定是成对出现，即一个X里面的一个Y里面的），但是没关系，因为他们在后面因为VISIT=0，所以不改变值
break;
int dx = -inf;
for(int i=1;i!=n;i++)
{
if(vis_x[i])//X中在相等子图的 {
for(int j=1;j!=n;j++)
{
if(!vis_y[j])//y不在相等子图中 dx = min(dx,lx[i]+ly[j]-bin_map[i][j]);
}
}
}
for(int i=1;i!=n+1;i++)
{//修改时对所有VISIT过的节点修改，原因就是上面提到的四条
if(vis_x[i])
lx[i]-=dx;
if(vis_y[i])
ly[i]+=dx;
}
}
}
int sum = 0;
for(int i=1;i!=n;i++)
{
sum-=bin_map[result[i]][i];//result标记最后想要的值
}
return sum;
}
int main()
{
int m,n;
while(cin>>m>>n&&(m!=0&&n!=0))
{
vector<node> men;
vector<node> house;
int count_m(0);
count_h=0;
for(int i=1;i!=m+1;i++)
{
for(int j=1;j!=n+1;j++)
{
cin>>ch[i][j];
if(ch[i][j]==‘m‘)
{
count_m++;
node N;N.pos_x = j;N.pos_y = i;N.node_num = count_m;
men.push_back(N);
}
if(ch[i][j]==‘H‘)
{
count_h++;
node N;N.pos_x = j;N.pos_y = i;N.node_num = count_h;
house.push_back(N);
}
}
}
memset(bin_map,0,sizeof(bin_map));
for(vector<node> ::size_type t=0;t!=house.size();t++)//构造二分图
{
node N1 = men[t];
for(vector<node> ::size_type i=0;i!=house.size();i++)
{
int x2 = house[i].pos_x;int y2 = house[i].pos_y;
int x1 = N1.pos_x;int y1 = N1.pos_y;
int num = -(abs(x1-x2)+abs(y1-y2));//值变为负数转化为，求最大匹配
//KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可
bin_map[N1.node_num][house[i].node_num] = num;
}
}
int cost = best_match(count_m+1);
cout<<cost<<endl;
}
return 0;
}
以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，
复杂度为O(n2)。
实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数 slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，
检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A [i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为
d值即可,即在DFS阶段就得到该减的东西，而不是重新回头找）。
#include <iostream>
using namespace std;
const int maxn = 105;
const int inf = 1000000000;
typedef struct Man
{
int x,y;
}Man;
int map[maxn][maxn];
bool x[maxn],y[maxn];
int my[maxn];
int lx[maxn],ly[maxn];
int slack[maxn];
bool dfs(int t,int N)
{
int u;
int wt;
x[t] = 1;
for(u=1;u<=N;u++)
{
wt = map[t][u]-lx[t]-ly[u];
if(!y[u]&&!wt)
{
y[u] = 1;
if(my[u]==-1||dfs(my[u],N))
{
my[u] = t;
return true;
}
}
else if(y[u]==0 && slack[u]>wt) slack[u] = wt;//不满足。如果y[u]=0, map[t][u]!=lx[t]+ly[u]，恰恰是我门需要修改的增广路，对于y[u]=1的情况，没有必要存储
}
return false;
}
int perfect_match(int N)
{
int i,j,k;
for(i=1;i<=N;i++)
{
my[i] = -1;
ly[i] = 0;
lx[i] = inf;//求最小权这样,最大权应该是-inf;
for(j=1;j<=N;j++)
if(map[i][j]<lx[i])lx[i] = map[i][j];//求最小权，因此起始状态是lx[]+ly[]<=map[i][j],lx[i]是i点上边最小的那个，ly是0.只有正确匹配，map[i][j]//才能取得最小值
}
for(k=1;k<=N;k++)
{
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(i=1;i<=N;i++) slack[i] = inf;
while(!dfs(k,N))
{
int d = inf;
for(i=1;i<=N;i++)
if(slack[i]<d) d = slack[i];//slack里面存储的全部是Y[I]=0的
for(i=1;i<=N;i++)
{
if(x[i]) {lx[i]+=d; x[i] = 0;}//最小权和，之前 lx[]+ly[]<map[i][j]，为使得等式成立，LX变大
if(y[i]) {ly[i]-=d; y[i] = 0;}//
}
}
}
int ans = 0;
for(i=1;i<=N;i++)
ans+=map[my[i]][i];
return ans;
}
int main()
{
int i,j,k,l;
int n,m;
char an[maxn][maxn];
Man M[maxn],Hou[maxn];
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
k = l = 0;
for(i=0;i<n;i++)
{ scanf("%s",an[i]);
for(j=0;j<m;j++)
{
if(an[i][j]==‘m‘){M[++k].x = i; M[k].y = j;}
if(an[i][j]==‘H‘){Hou[++l].x = i; Hou[l].y = j;}
}
}
for(i=1;i<=k;i++)
for(j=1;j<=l;j++)
{
map[i][j] = (abs(M[i].x-Hou[j].x)+abs(M[i].y-Hou[j].y));
}
printf("%d\n",perfect_match(k));
}
}
Bipartitegraph2195EM