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

## 为什么不能过？求大牛解答！！！

Posted by likit at 2010-01-26 12:47:50 on Problem 2195
```#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>

using namespace std;

#define  Max( x, y ) ( ((x) > (y)) ? (x) : (y) )
#define  Min( x, y ) ( ((x) < (y)) ? (x) : (y) )
#define oo 2147483647

struct pt
{
int x,y;
pt()
{
x = y = 0;
}
};

int mat[555][555],m,n;
pt man[555],h[555];
int numofm,numofh;

int w[555][555],visitedx[555],visitedy[555],match[555];
int lx[555],ly[555];

void init()
{
for(int i = 0;i < numofm;i++)
for(int j = 0;j < numofh;j++)
w[i][j] = abs(man[i].x - h[j].x) + abs(man[i].y - h[j].y);
}

bool path(int u)
{
visitedx[u] = 1;
for(int v = 0;v < numofh;v++)
{
if(!visitedy[v] && lx[u] + ly[v] == w[u][v])
{
visitedy[v] = 1;
if(match[v] == -1 || path(match[v]))
{
match[v] = u;
return 1;
}
}
}
return 0;
}

void solve()
{
init();
for(int i = 0;i < numofm;i++)
for(int j = 0;j < numofh;j++)
w[i][j] = -w[i][j];

for(int i = 0;i < numofm;i++)
{
ly[i] = 0;
lx[i] = -oo;
for(int j = 0;j < numofh;j++)
lx[i] = Max(lx[i],w[i][j]);
}

memset(match,-1,sizeof(match));

for(int u = 0;u < numofm;u++)
{
while(1)
{
memset(visitedx,0,sizeof(visitedx));memset(visitedy,0,sizeof(visitedy));
if(path(u))	break;

int dx = oo;
for(int i = 0;i < numofm;i++)
if(visitedx[i])
for(int j = 0;j < numofh;j++)
if(!visitedy[j])
dx = Min(dx,lx[i] + ly[j] - w[i][j]);

for(int i = 0;i < numofm;i++)
{
if(visitedx[i])	lx[i] -= dx;
if(visitedy[i])	ly[i] += dx;
}
}
}

int ans = 0;
for(int i = 0;i < numofh;i++)
ans += w[match[i]][i];
ans = -ans;
cout<<ans<<endl;
}

int main()
{
while(cin>>n>>m)
{
if(n == 0 && m == 0)	break;
memset(mat,0,sizeof(mat));memset(lx,0,sizeof(lx));memset(ly,0,sizeof(ly));memset(w,0,sizeof(w));
numofm = numofh = 0;
for(int i = 0;i < n;i++)
{
fflush(stdin);
for(int j = 0;j < m;j++)
{
char ch;cin>>ch;
if(ch == 'm')
{
man[numofm].x = i;
man[numofm].y = j;
numofm++;
}
if(ch == 'H')
{
h[numofh].x = i;
h[numofh].y = j;
numofh++;
}
}
}
solve();
}

return 0;
}```

Followed by:

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

Content:

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