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<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<string> #include<cmath> #include<vector> #include<stack> #include<queue> #include<map> #include<set> using namespace std; const int Inf=0x3f3f3f3f; const int M=105; int n,m,hh,mm; int mp[M][M],lx[M],ly[M],match[M],vx[M],vy[M]; typedef struct { int x,y; }node; node HH[M],MM[M]; int hungery(int u) { int i; vx[u]=1; for(i=0;i<hh;i++) { if(!vy[i]&&lx[u]+ly[i]==mp[u][i]) { vy[i]=1; if(match[i]==-1||hungery(match[i])) { match[i]=u; return 1; } } } return 0; } void KM() { int i,j,z; for(i=0;i<mm;i++) lx[i]=-Inf; for(i=0;i<mm;i++) for(j=0;j<hh;j++) lx[i]=max(lx[i],mp[i][j]); memset(match,-1,sizeof(match)); memset(ly,0,sizeof(ly)); for(i=0;i<mm;i++) { while(1) { memset(vx,0,sizeof(vx)); memset(vy,0,sizeof(vy)); if(hungery(i)) break; int temp=Inf; for(j=0;j<mm;j++) if(vx[j]) for(z=0;z<hh;z++) if(!vy[z]&&temp>lx[j]+ly[z]-mp[j][z]) temp=lx[j]+ly[z]-mp[j][z]; for(j=0;j<mm;j++) if(vx[j]) lx[j]-=temp; for(j=0;j<hh;j++) if(vy[j]) ly[j]+=temp; } } } int main() { int i,j,sum; char Map[M][M]; while(~scanf("%d%d",&n,&m),n+m) { for(i=0;i<n;i++) scanf("%s",Map[i]); hh=mm=0; for(i=0;i<n;i++) for(j=0;j<m;j++) if(Map[i][j]=='m') MM[mm].x=i,MM[mm++].y=j; else if(Map[i][j]=='H') HH[hh].x=i,HH[hh++].y=j; for(i=0;i<mm;i++) for(j=0;j<hh;j++) mp[i][j]=-(abs(MM[i].x-HH[j].x)+abs(MM[i].y-HH[j].y)); KM(); sum=0; for(i=0;i<hh;i++) if(match[i]!=-1) sum+=mp[match[i]][i]; printf("%d\n",-sum); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator