Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

KM算法

Posted by ACAccepted at 2019-06-28 16:48:42 on Problem 2195
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN=105;
const int MAXM=5005;
const int INF=0x3f3f3f3f;
int n,m,now,cnt1,cnt2;
char s[MAXN][MAXN];
int map[MAXN][MAXN];
int match[MAXM],slack[MAXM];
int vis_boy[MAXM],vis_girl[MAXM];
int ex_boy[MAXM],ex_girl[MAXM],rela[MAXM][MAXM];

inline int abs(int x)
{
	if (x<0) return -x;
	return x;
}

inline int get_cost(int x,int y,int x0,int y0)
{
	return abs(x-x0)+abs(y-y0);
}

inline bool dfs(int x)
{
	int cp;
	vis_girl[x]=now;
	for (int y=1;y<=cnt1;y++)
	{
		if (vis_boy[y]==now) continue;
		cp=ex_girl[x]+ex_boy[y]-rela[x][y];
		if (cp==0)
		{
			vis_boy[y]=now;
			if ((match[y]==0)||dfs(match[y]))
			{
				match[y]=x;return true;
			}
		}
		else if (cp<slack[y]) slack[y]=cp;
	}
	return false;
}

inline long long KM()
{
	for (int i=1;i<=cnt1;i++)
	{
		match[i]=ex_boy[i]=ex_girl[i]=0;
		for (int j=1;j<=cnt1;j++)
			if (rela[i][j]>ex_girl[i]) ex_girl[i]=rela[i][j];
	}
	for (int i=1;i<=cnt1;i++)
	{
		now=0;
		for (int j=1;j<=cnt1;j++)
		{
			slack[j]=INF;
			vis_boy[j]=vis_girl[j]=0;
		}
		while (true)
		{
			now++;
			if (dfs(i)) break;
			int d=INF;
			for (int j=1;j<=cnt1;j++) if (vis_boy[j]!=now&&slack[j]<d) d=slack[j];
			for (int j=1;j<=cnt1;j++)
			{
				if (vis_girl[j]==now) ex_girl[j]-=d;
				if (vis_boy[j]==now) ex_boy[j]+=d;
				else slack[j]-=d;
			}
		}
	}
	long long ans=0;
	for (int i=1;i<=cnt1;i++) ans+=rela[match[i]][i];
	return ans;
}

int main()
{
	while (~scanf("%d%d",&n,&m))
	{
		if (n==0&&m==0) break;
		cnt1=0;cnt2=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++) 
			{
				cin>>s[i][j];
				if (s[i][j]=='m') map[i][j]=++cnt1;
				if (s[i][j]=='H') map[i][j]=++cnt2;
			}
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				if (s[i][j]=='m')
					for (int x=1;x<=n;x++)
						for (int y=1;y<=m;y++)
							if (s[x][y]=='H') rela[map[i][j]][map[x][y]]=-get_cost(i,j,x,y);
		printf("%lld\n",-KM());
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator