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

## AC~~~~

Posted by root123 at 2012-10-23 23:06:21 on Problem 2195
```#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 100300
#define maxm 200003
#define inf 1000000000

int min(int a, int b)
{
return a < b ? a : b;
}

struct E
{
int u, v, c, w, next;
}edge[maxm<<3];

int n, m;
int S, T;

void init()
{
tot = 0;
}

void add(int s, int t, int c, int w)
{
edge[tot].u = s;
edge[tot].v = t;
edge[tot].c = c;
edge[tot].w = w;

edge[tot].u = t;
edge[tot].v = s;
edge[tot].c = 0;
edge[tot].w = -w;
}

bool vis[maxn];
int pre[maxn];
int dis[maxn];
bool spfa(int s, int t, int n)
{
int i, u, v;
queue<int> q;
for(i = 0; i <= n; i++)
vis[i] = 0, pre[i] = -1, dis[i] = inf;
vis[s] = 1; dis[s] = 0;
q.push(s);
while(!q.empty())
{
u = q.front(); q.pop(); vis[u] = 0;
for(i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(edge[i].c && dis[v] > dis[u] + edge[i].w)
{
dis[v] = dis[u] + edge[i].w;
pre[v] = i;
if(!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
}
if(dis[t] == inf) return 0;
return 1;
}

int mfmw(int s, int t, int n)
{
int maxf = 0;
int i, aug, minw = 0;
while(spfa(s, t, n))
{
aug = inf;
for(i = pre[t]; i != -1; i = pre[edge[i].u])
aug = min(aug, edge[i].c);
maxf += aug;
for(i = pre[t]; i != -1; i = pre[edge[i].u])
{
edge[i].c -= aug;
edge[i^1].c += aug;
}
minw += dis[t] * aug;
}
return minw;
}

char map[303][303];

struct node
{
int x, y;
node(){}
node(int xx, int yy): x(xx), y(yy){};
}a[303], b[303];
int main()
{
int i, j;
int x, y, z;
while( ~scanf("%d%d", &n, &m))
{
if(!n || !m) break;
init();
S = 0; T = n * m + 1;
int p = 0, q = 0;
for(i = 1; i <= n; i++)
{
scanf("%s", map[i]+1);
for(j = 1; j <= m; j++)
{
x = (i-1)*m+j;
if(map[i][j] == 'm')
add(S, x, 1, 0), a[p++] = node(i, j);
if(map[i][j] == 'H')
add(x, T, 1, 0), b[q++] = node(i, j);
}
}
for(i = 0; i < p; i++)
for(j = 0; j < q; j++)
add(a[i].x*m+a[i].y-m, b[j].x*m+b[j].y-m, 1, abs(a[i].x - b[j].x) + abs(a[i].y - b[j].y));
printf("%d\n", mfmw(S, T, T+1));

}
return 0;
} ```

Followed by: