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