1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N=210,inf=0x3f3f3f3f; struct node{int x,y;}H[N],M[N];int Hlen,Mlen; struct edge{int x,y,f,c,pre;}a[N*N];int alen,last[N],cur[N]; void ins(int x,int y,int f,int c) { a[++alen]={x,y,f,c,last[x]};last[x]=alen; a[++alen]={y,x,0,-c,last[y]};last[y]=alen; } char ch[N][N]; int n,m,st,ed,d[N],v[N],ans; int dis(node a,node b){return abs(a.x-b.x)+abs(a.y-b.y);} bool spfa() { memset(d,0x3f,sizeof(d));d[st]=0; memset(v,0,sizeof(v));v[st]=1; queue<int>Q;Q.push(st); while(!Q.empty()) { int x=Q.front();Q.pop();v[x]=0; for(int k=last[x];k;k=a[k].pre)if(a[k].f) { int y=a[k].y; if(d[y]>d[x]+a[k].c) { d[y]=d[x]+a[k].c; if(!v[y])Q.push(y),v[y]=1; } } } return (d[ed]!=inf); } int dinic(int x,int f) { if(x==ed){ans+=d[ed]*f;return f;} int sx=0; v[x]=1; for(int k=last[x];k;k=a[k].pre)if(a[k].f) { cur[x]=k; int y=a[k].y;if(v[y])continue; if(d[y]==d[x]+a[k].c) { int sy=dinic(y,min(f-sx,a[k].f)); a[k].f-=sy,a[k^1].f+=sy; sx+=sy;if(sx==f) return f; } } if(sx>0)v[x]=0; return sx; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0) break; for(int i=1;i<=n;i++)scanf("%s",ch[i]+1); Hlen=0,Mlen=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) { if(ch[i][j]=='H')H[++Hlen]={i,j}; if(ch[i][j]=='m')M[++Mlen]={i,j}; } alen=1;memset(last,0,sizeof(last)); for(int i=1;i<=Mlen;i++)for(int j=1;j<=Hlen;j++)ins(i,j+Mlen,1,dis(M[i],H[j])); st=Mlen+Hlen+1,ed=st+1; for(int i=1;i<=Mlen;i++)ins(st,i,1,0); for(int i=1;i<=Hlen;i++)ins(i+Mlen,ed,1,0); ans=0; while(spfa()) { memcpy(cur,last,sizeof(last)); int t=dinic(st,inf); } printf("%d\n",ans); } return 0; }
- 1
信息
- ID
- 1497
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 6
- 标签
- 递交数
- 67
- 已通过
- 21
- 上传者