1 条题解

  • 0
    @ 2025-5-19 23:52:39
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<queue>
    #include<map>
    #include<algorithm>
    #include<set>
    using namespace std;
    const int INF=0x7fffffff;
    const int MAXN=100005;
    int N,M;
    char grid[105][105];
    int dis[MAXN];
    int vis[MAXN];
    int pre[MAXN];
    struct Edge
    {
          int u;
          int v;
          int cap;
          int cost;
          int next;
    }edge[4*MAXN];
    int edgecount;
    int head[MAXN];
    void Init()
    {
          memset(head,-1,sizeof(head));
          edgecount=0;
    }
    void Add_edge(int u,int v,int cap,int cost)
    {
          edge[edgecount].u=u;edge[edgecount].v=v;edge[edgecount].cap=cap;
          edge[edgecount].cost=cost;edge[edgecount].next=head[u];
          head[u]=edgecount++;
          edge[edgecount].u=v;edge[edgecount].v=u;edge[edgecount].cap=0;
          edge[edgecount].cost=-cost;edge[edgecount].next=head[v];
          head[v]=edgecount++;
    }
    bool spfa(int s,int t ,int n)//0表示没有增广路
    {
          for(int i=0;i<=n;i++)
          {
                dis[i]=INF;
                vis[i]=0;
                pre[i]=-1;
          }
          dis[s]=0;
          vis[s]=1;
          queue<int> Q;
          Q.push(s);
          while(!Q.empty())
          {
                int u=Q.front();
                Q.pop();
                vis[u]=0;
                for(int k=head[u];k!=-1;k=edge[k].next)
                {
                      int v=edge[k].v;
                      int cost=edge[k].cost;
                      if(edge[k].cap && dis[v]> dis[u]+cost)
                      {
                            dis[v]=dis[u]+cost;
                            pre[v]=k;
                            if(!vis[v])
                            {
                                  vis[v]=1;
                                  Q.push(v);
                            }
                      }
                }
          }
          if(dis[t]==INF)return 0;
          return 1;
    }
    void MCMF(int s,int t,int n)
    {
          int minflow;
          int mincost=0;
          while(spfa(s,t,n))
          {
                minflow=INF;
                for(int k=pre[t];k!=-1;k=pre[edge[k].u])
                {
                      minflow=min(minflow,edge[k].cap);
                }
                for(int k=pre[t];k!=-1;k=pre[edge[k].u])
                {
                      edge[k].cap-=minflow;
                      edge[k^1].cap+=minflow;
                }
                mincost+=dis[t];
          }
          cout<<mincost<<endl;
    }
    int get_num(int i,int j)//第i行第j列格子的编号
    {
          return (i-1)*M+j;
    }
    bool is_out(int x,int y)
    {
          if(x<1 || x>N || y<1 || y>M)return 1;
          else return 0;
    }
    void Build()//建图
    {
          for(int i=1;i<=N;i++)
          {
                for(int j=1;j<=M;j++)
                {
                      if(!is_out(i-1,j))Add_edge(get_num(i,j),get_num(i-1,j),INF,1);
                      if(!is_out(i+1,j))Add_edge(get_num(i,j),get_num(i+1,j),INF,1);
                      if(!is_out(i,j-1))Add_edge(get_num(i,j),get_num(i,j-1),INF,1);
                      if(!is_out(i,j+1))Add_edge(get_num(i,j),get_num(i,j+1),INF,1);
    
                      if(grid[i][j]=='m')Add_edge(0,get_num(i,j),1,0);
                      else if(grid[i][j]=='H')Add_edge(get_num(i,j),N*M+1,1,0);
                }
          }
    }
    int main()
    {
        while(scanf("%d%d",&N,&M)!=EOF)
        {
              if(N==0 && M==0)break;
              for(int i=1;i<=N;i++)
                     for(int j=1;j<=M;j++)
                     {
                         scanf("%c",&grid[i][j]);
                         while(grid[i][j]==' ' || grid[i][j]=='\n') scanf("%c",&grid[i][j]);
                     }
              Init();
              Build();
              MCMF(0,N*M+1,N*M+2);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1196
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    1
    上传者