今天學了KM算法，用于二分圖的完美匹配，以前就遇到過很多次，但是一直都沒有花時間去學
學的比較挫，寫的是n^4的算法
實際上有m*m*n的算法的
下邊幾道是完美匹配的題目
http://info.zjfc.edu.cn/acm/problemDetail.aspx?pid=1222
赤裸裸的完美匹配，圖都建好了
http://acm.hdu.edu.cn/showproblem.php?pid=1533
這個建圖很容易
http://acm.hdu.edu.cn/showproblem.php?pid=2282
這個需要建圖
下邊是http://acm.hdu.edu.cn/showproblem.php?pid=1533
的AC代碼
//////////////////////////////////////////////////////////////////////////
//二分圖的完美匹配，Kuhn－Munkras算法
#include<stdio.h>
#include<math.h>
#include<string>
#define MAXN 101
//////////////////////////////////////////////////////////////////////////
#define inf 0x7FFFFFFF
int edge[MAXN][MAXN];
int match[MAXN];
bool hash[MAXN][MAXN];
bool xhash[MAXN],yhash[MAXN];
char map[MAXN][MAXN];
int min(int a,int b){return a>b?b:a;}
int max(int a,int b){return a>b?a:b;}
void Scanf(int n,int m,int &l);
bool dfs(int p,int n)//找增廣路徑
{
int i;
for(i=0;i<n;i++)
{
if(!yhash[i] && hash[p][i])
{
yhash[i] = true;
int t = match[i];
if(t == -1 || dfs(t,n))
{
match[i] = p;
return true;
}
if(t != -1)
xhash[t] = true;
}
}
return false;
}
void show(int id,int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(id)
printf("%d ",edge[i][j]);
else
printf("%d ",hash[i][j]);
}
puts("");
}
puts("");
}
void KM_Perfect_Match(int n)
{
int i,j;
int xl[MAXN],yl[MAXN];
for(i=0;i<n;i++)
{
xl[i] = 0;
yl[i] = 0;
for(j=0;j<n;j++)
xl[i] = max(xl[i],edge[i][j]);
}
bool perfect = false;
while(!perfect)
{
for(i=0;i<n;i++)//現(xiàn)階段已經(jīng)匹配的路
{
for(j=0;j<n;j++)
{
if(xl[i] + yl[j] == edge[i][j])
hash[i][j] = true;
else
hash[i][j] = false;
}
}
// show(0,n);
int cnt = 0;
memset(match,-1,sizeof(match));
for(i=0;i<n;i++)//當前的圖是否能全部匹配
{
memset(xhash,false,sizeof(xhash));
memset(yhash,false,sizeof(yhash));
if(dfs(i,n))
cnt ++;
else
{
xhash[i] = true;
break;
}
}
if(cnt == n)//沒有增廣路徑
perfect = true;
else
{
int ex = inf;
for(i=0;i<n;i++)
{
for(j=0;xhash[i] && j<n;j++)
{
if(!yhash[j])
ex = min(ex,xl[i] + yl[j] - edge[i][j]);//找到一條沒建的邊的最小值
}
}
for(i=0;i<n;i++)//根據(jù)這個邊來進行松弛
{
if(xhash[i])
xl[i] -= ex;
if(yhash[i])
yl[i] += ex;
}
}
}
}
int main()
{
int n,m,l;
while(scanf("%d%d",&n,&m))
{
if(n == 0 && m == 0)
break;
Scanf(n,m,l);
KM_Perfect_Match(l);
int mindis = 0;
for(int i=0;i<l;i++)
mindis += edge[match[i]][i];
printf("%d\n",-mindis);
}
return 0;
}
//讀入建圖
void Scanf(int n,int m,int &l)
{
int i,j,l1,l2;
struct Point{
int x,y;
}MAN[MAXN],HOUSE[MAXN];
l1 = l2 = 0;
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
for(j=0;j<m;j++)
{
if(map[i][j]=='m')
{
MAN[l1].x = i;
MAN[l1].y = j;
l1 ++;
}
else if(map[i][j]=='H')
{
HOUSE[l2].x = i;
HOUSE[l2].y = j;
l2 ++;
}
}
}
l = l1;
for(i=0;i<l;i++)
for(j=0;j<l;j++)
edge[i][j] = -abs(MAN[i].x - HOUSE[j].x) - abs(MAN[i].y - HOUSE[j].y);
}
posted on 2009-04-21 14:32
shǎ崽 閱讀(1775)
評論(2) 編輯 收藏 引用