Going Home(MCMF)

题意：在一个n*m的图中，'m'代表人，'H'代表房子，人每移动一次的费用为1，求所有人移动到房子里的最小花费。

思路：最小费用最大流问题。关键是建图，建好图后就是MCMF的模板题了。。

关于建图：增加一个原点S，一个汇点T, S与所有人相连，容量为1，花费为0；每个人与所有房子相连，容量为1，花费为|人与房子的水平距离|+|人与房子的垂直距离|；最后所有的房子与汇点相连，容量为1，花费为0。

关于算法：多次spfa找增广路，然后求最大流。最小花费+=原点到汇点的最小距离*每次增光后的最大流量

 #include <stdio.h>

 #include <iostream>

 #include <stdlib.h>

 #include <algorithm>

 #include <string.h>

 #include <queue>

 using namespace std;

 const int N=;

 const int INF=<<;

 struct node

 {

     int x,y;

 } m[N],h[N];

 int cap[N][N],cost[N][N];

 int pre[N],vis[N],dis[N];

 int cntm,cnth,t;

 int spfa()

 {

     queue<int>q;

     for (int i = ; i <= t; i++)

     {

         dis[i] = INF;

         vis[i] = ;

         pre[i] = -;

     }

     dis[]=;

     q.push();

     vis[] = ;

     while(!q.empty())

     {

         int u = q.front();

         vis[u] = ;

         q.pop();

         for (int i = ; i <= t; i++)

         {

             if (cap[u][i]&&dis[i]>dis[u]+cost[u][i])

             {

                 pre[i] = u;

                 dis[i] = dis[u]+cost[u][i];

                 if (!vis[i])

                 {

                     q.push(i);

                     vis[i] = ;

                 }

             }

         }

     }

     if (dis[t]==INF)

         return ;

     return ;

 }

 int MCMF()

 {

     int Maxflow = INF;

     int Mincost = ;

     while(spfa())

     {

         int u = t;

         while(pre[u]!=-)

         {

             Maxflow = min(Maxflow,cap[pre[u]][u]);

             u = pre[u];

         }

         Mincost += dis[t]*Maxflow;

         u = t;

         while(pre[u]!=-)

         {

             cap[pre[u]][u]-=Maxflow;

             cap[u][pre[u]]+=Maxflow;

             u = pre[u];

         }

     }

     return Mincost;

 }

 void build()

 {

     for (int i = ; i <= cntm; i++)

     {

         for (int j = ; j <= cnth; j++)

         {

             cap[i][j+cntm] = ;

             cost[i][j+cntm] = abs(m[i].x-h[j].x)+abs(m[i].y-h[j].y);

             cost[j+cntm][i] = -cost[i][j+cntm];

         }

     }

     for (int i = ; i <= cntm; i ++)

     {

         cap[][i] = ;

         cost[][i] = ;

         cap[i+cntm][t] = ;

         cost[i+cntm][t] = ;

     }

 }

 int main()

 {

     int row,col;

     while(~scanf("%d%d",&row,&col))

     {

         if (row==&&col==)

             break;

         char ch;

         cntm = ,cnth = ;

         memset(cap,,sizeof(cap));

         memset(cost,,sizeof(cost));

         for (int i = ; i <= row; i++)

         {

             for (int j = ; j <= col; j++)

             {

                 cin>>ch;

                 if (ch=='m')

                 {

                     m[++cntm].x = i;

                     m[cntm].y = j;

                 }

                 if (ch=='H')

                 {

                     h[++cnth].x = i;

                     h[cnth].y = j;

                 }

             }

         }

         t = cnth+cntm+;

         build();

         int Mincost = MCMF();

         printf("%d\n",Mincost);

     }

     return ;

 }

巴特西

Going Home(MCMF)

最新文章

热门文章