POJ - 2195 Going Home 费用流+BFS-白红宇的个人博客

POJ - 2195 Going Home 费用流+BFS

发布日期：2021-05-10 11:28:36 浏览次数：21 分类：精选文章

本文共 2879 字，大约阅读时间需要 9 分钟。

题目链接

题意

给出n*m网格，中间有多个小人和房子，小人走一步花1￥，要求所有小人都到家（人房无对应关系），求最小花费

思路

第一眼以为是最短路，但由于小人和房子无对应关系，也就是一个小人选择不同房子会影响别的小人，所以直接最短路肯定wa的。

因为每个小人都要回一个房子，在这个基础上求最小花费。所以可以套费用流，超级源点向小人连边权1，房子向汇点连边权1，那么再来建立小人-房子的关系，费用流跑出来是最大流条件下（人人有房住）下最小花费，就是答案了。

具体小人-房子的联系，就遍历全图，对每一个小人跑bfs就行了。

代码

#include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
              #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define endl "\n"//#define int long longusing namespace std; typedef long long ll; const int maxn=205; const int maxe=30005; const int inf=0x3f3f3f3f; int n,m,s,t,cnt; int gh[maxn][maxn]; int head[maxn]; struct Edge{ int v,w,next,flow; }edge[maxe]; int dis[maxn],incf[maxn],pre[maxn];//incf最小流量 bool inque[maxn]; int maxflow,mincost; //费用流模版 void init(){ memset(head,-1,sizeof(head)); maxflow=mincost=0; cnt=0; } void add(int u,int v,int flow,int cost){ //cout<
             <<" "<
              
               <<" "<
               
                <<" "<
                
                 <

q; memset(dis,0x3f,sizeof(dis)); memset(inque,0,sizeof(inque)); q.push(s); dis[s]=0; inque[s]=1; incf[s]=inf; while(q.size()){ int u=q.front();q.pop(); inque[u]=0; for(int i=head[u];~i;i=edge[i].next){ if(!edge[i].flow) continue; int v=edge[i].v; if(dis[v]>dis[u]+edge[i].w){ dis[v]=dis[u]+edge[i].w; incf[v]=min(incf[u],edge[i].flow); pre[v]=i; if(!inque[v]){ q.push(v); inque[v]=1; } } } } if(dis[t]==inf) return 0; return 1; } void MCMF(){ while(spfa()){ int x=t; maxflow+=incf[t]; mincost+=dis[t]*incf[t]; int i; while(x!=s){ i=pre[x]; edge[i].flow-=incf[t]; edge[i^1].flow+=incf[t]; x=edge[i^1].v; } } } //bfs建图 int dxy[][2]={ { 1,0},{ -1,0},{ 0,1},{ 0,-1}}; bool vis[maxn][maxn]; int dis_bfs[maxn][maxn]; inline bool ju(int x,int y){ if(x<1||x>n||y<1||y>m||vis[x][y]) return 0; return 1; } void find(int x,int y){ memset(vis,0,sizeof vis); queue

>q; pair

p; q.push(make_pair(x,y)); dis_bfs[x][y]=0; vis[x][y]=1; while(q.size()){ p=q.front(),q.pop(); //找到了房子，连边 if(gh[p.first][p.second]<0){ add(gh[x][y],-gh[p.first][p.second]+100,1,dis_bfs[p.first][p.second]); add(-gh[p.first][p.second]+100,gh[x][y],0,-dis_bfs[p.first][p.second]); } for(int i=0;i<4;i++){ int tx=p.first+dxy[i][0],ty=p.second+dxy[i][1]; if(ju(tx,ty)){ vis[tx][ty]=1; q.push(make_pair(tx,ty)); dis_bfs[tx][ty]=dis_bfs[p.first][p.second]+1; } } } } int main(){ while(scanf("%d%d",&n,&m)==2){ if(!n&&!m) break; s=201,t=202; init(); getchar(); int cnt1=1,cnt2=-1;//编号 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ char ch=getchar(); while(ch=='\n'||ch==' ') ch=getchar(); if(ch=='.') gh[i][j]=0; else if(ch=='m') gh[i][j]=cnt1++; else gh[i][j]=cnt2--; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(gh[i][j]>0) find(i,j); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(gh[i][j]>0){ //源点-人 add(s,gh[i][j],1,0); add(gh[i][j],s,0,0); } else if(gh[i][j]<0){ //房子-汇点 add(-gh[i][j]+100,t,1,0); add(t,-gh[i][j]+100,0,0); } MCMF(); printf("%d\n",mincost); } }

上一篇：POJ - 2516 Minimum Cost 费用流，拆图

下一篇：POJ - 1087 A Plug for UNIX 最大流超级源汇

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题意

思路

代码

发表评论

最新留言

关于作者

推荐文章