Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: