| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么不能过?求大牛解答!!!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator