1 条题解

  • 0
    @ 2025-10-8 16:57:37
    #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
    上传者