poj 2195 KM算法

题目链接：http://poj.org/problem?id=2195

KM算法模板~

代码如下：

#include "stdio.h"
#include "string.h"
#include "queue"
#include "math.h"
using namespace std;

#define N 210
#define INF 0x3fffffff

struct node{
	int u,v,w,k;
	int next;
}edge[4*N*N];

struct point{
	int x,y;
}people[N],house[N];

bool mark[N];
int start,end;
int n,ans,idx;
int dis[N],route[N],head[N];

void init();
bool SPFA();
void EK();
void adde(int u,int v,int w,int k);
void addedge(int u,int v,int w,int k);

int main()
{
	int L,D;
	int i,j;
	int x,y,w;
	char map[105][105];
	while(scanf("%d%d",&L,&D),L&&D)
	{
		for(i=1;i<=L;i++)
			scanf("%s",map[i]+1);
		x=y=0;
		for(i=1;i<=L;i++)
		{
			for(j=1;j<=D;j++)
			{
				if(map[i][j]=='m'){	people[x].x = i;	people[x].y = j;  x++;}
				if(map[i][j]=='H'){ house[y].x = i;		house[y].y = j;	  y++;}
			}
		}
		init();
		n=x;
		start = 0;   //起点
		end = n+n+1;   //终点
		for(i=1;i<=n;i++)
			adde(start,i,0,1); //1~n每个点代表人
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)  //n+1~n+n每个点代表house
			{
				w = abs(people[i-1].x-house[j-1].x)+abs(people[i-1].y-house[j-1].y);
				adde(i,j+n,w,1);
			}
		}
		for(i=1;i<=n;i++)
			adde(i+n,end,0,1);
		while(SPFA())
			EK();
		printf("%d
",ans);
	}
	return 0;
}	

void init()
{
	ans = 0;
	idx = 0;
	memset(head,-1,sizeof(head));
}

void adde(int u,int v,int w,int k)
{
	addedge(u,v,w,k);
	addedge(v,u,-w,0);
}

void addedge(int u,int v,int w,int k)
{
	edge[idx].u = u;
	edge[idx].v = v;
	edge[idx].w = w;
	edge[idx].k = k;
	edge[idx].next = head[u];
	head[u] = idx;
	idx++;
}

bool SPFA()
{
	int i;
	int x,y;
	memset(route,-1,sizeof(route));
	memset(mark,false,sizeof(mark));
	for(i=0;i<N;i++)	dis[i] = INF;
	dis[0] = 0;
	queue<int> q;
	q.push(start);
	mark[start] = true;
	while(!q.empty())
	{
		x = q.front();
		q.pop();
		mark[x] = false;
		for(i=head[x];i!=-1;i=edge[i].next)
		{
			y = edge[i].v;
			if(edge[i].k && dis[y]>dis[x]+edge[i].w)
			{
				route[y] = i;
				dis[y] = dis[x] + edge[i].w;
				if(mark[y]==false)
				{
					mark[y] = true;
					q.push(y);
				}
			}
		}	
	}
	route[0] = -1;
	if(route[end]==-1) return false;
	return true;
}

void EK()
{
	int x,y;
	y = route[end];
	while(y!=-1)
	{
		x = y^1;
		ans+=edge[y].w;
		edge[y].k--;
		edge[x].k++;
		y = route[edge[y].u];
	}
}