Going Home(最小费用最大流)

最大流算法的一种实现就是不断寻找增广路径，一般推荐用BFS。最小费用最大流算法其实就是最大流算法的增强版，限制了路径搜索算法必须为最短路径算法，其中路径的权值即是费用。

算法本身不难，难在构图。通常需要构建超级汇点和超级源点，还有就是逆向路径的权值要设成正向路径权值的相反数，这点很关键。

#include
#include
using namespace std;
#define ABS(x) (x<0?-x:x)
#define MAXN 205
#define MIN(x,y) (x
#define INF  200005
int map[MAXN][MAXN],cost[MAXN][MAXN];
int pre[MAXN],max_flow[MAXN];
//pre[] 记录结点的父节点 ; max_flow[] 记录从源点到当前点最多可以增加的容量，即限制值
int  flow[MAXN][MAXN];//记录当前网络中的流
int  dist[MAXN];//SPFA用
queue<int> my_queue;
bool in_queue[MAXN];
bool SPFA(int num,int source,int sink)
{
    memset(in_queue,0,sizeof(in_queue));
    memset(pre,-1,sizeof(pre));
    for(int i=0;i
    {
        dist[i]=INF;
    }
    dist[source]=0;
    my_queue.push(source);
    in_queue[source]=true;

    max_flow[source]=INF;
    while(!my_queue.empty())
    {
        int temp=my_queue.front();
        my_queue.pop();
        for(int i=0;i
        {
            if((map[temp][i]-flow[temp][i]>0)&&(dist[temp]+cost[temp][i]
            {
                dist[i]=dist[temp]+cost[temp][i];
                if(!in_queue[i])
                {
                    my_queue.push(i);
                    in_queue[i]=true;
                }
                pre[i]=temp;
                max_flow[i]=MIN(max_flow[temp],(map[temp][i]-flow[temp][i]));//求得max_flow
            }
        }
        in_queue[temp]=false;
    }
    if(pre[sink]!=-1) return true;//sink的父节点不为初始值，说明已经找到了一条路径
    return false;
/*

        Bellman-Ford(G,w,s) ：boolean                             //图G ，边集 函数 w ，s为源点

1        for each vertex v ∈ V（G） do            //初始化 1阶段

2            d[v] ←+∞

3        d[s] ←0;                          //1阶段结束

4        for i=1 to |v|-1 do              //2阶段开始，双重循环。

5        for each edge（u,v） ∈E(G) do//边集数组要用到,穷举每条边。

6              If d[v]> d[u]+ w(u,v) then  //松弛判断

7                 d[v]=d[u]+w(u,v)         //松弛操作   2阶段结束

8        for each edge（u,v） ∈E(G) do

9            If d[v]> d[u]+ w(u,v) then

10            Exit false

11    Exit true

*/

    //一开始想用bellman-ford
    //for(int i=0;i
    //{
    //  dist[i]=INF;
    //}
    //dist[source]=0;
    //memset(pre,-1,sizeof(pre));
    //max_flow[source]=INF;
    //  for(int j=0;j
    //  {
    //      for(int k=0;k
    //      {
    //          if((map[j][k]-flow[j][k]>0)&&(dist[j]+cost[j][k]
    //          {
    //              dist[k]=dist[j]+cost[j][k];
    //              pre[k]=j;
    //              max_flow[k]=MIN(max_flow[j],(map[j][k]-flow[j][k]));
    //          }
    //      }
    //  }
    //if(pre[sink]!=-1) return true;
    //else return false;
}
int sum_cost,sum_flow;//最终结果
void min_cost_max_flow(int num,int source,int sink)
//参数含义：结点数量  源点 汇点
{
    sum_cost=0,sum_flow=0;
    memset(flow,0,sizeof(flow));
    while(SPFA(num,source,sink))//一直循环，直到不存在增广最短路径
    {
        int k=sink;
        while(pre[k]>=0)
        {
            flow[pre[k]][k]+=max_flow[sink];   //将新的流量加入flow
            flow[k][pre[k]]=-flow[pre[k]][k];  //反向边,
            k=pre[k];
        }
        sum_cost+=dist[sink];                 //最小费用
        sum_flow+=max_flow[sink];             //费用最小时的最大流
    }
}
int main()
{
    int N,M,ans;
    char temp[MAXN];
    int house[MAXN][2],house_index;
    int people[MAXN][2],people_index;

    while(scanf("%d%d",&N,&M)&&N&&M)
    {
        memset(map ,0,sizeof(map));
        memset(cost,0,sizeof(cost));
        house_index=0;
        people_index=0;
        for(int i=0;i
        {
            scanf("%s",temp);
            for(int j=0;j
            {
                if(temp[j]=='H')
                {
                    house[house_index][0]=i;
                    house[house_index][1]=j;
                    house_index++;
                }
                else if(temp[j]=='m')
                {
                    people[people_index][0]=i;
                    people[people_index][1]=j;
                    people_index++;
                }
            }
        }
        for(int i=0;i
        {
            for(int j=0;j
            {
                cost[i][people_index+j]=ABS((people[i][0]-house[j][0]))+ABS((people[i][1]-house[j][1]));
                cost[people_index+j][i]=-cost[i][people_index+j];//逆向路径的权值要设成正向路径权值的相反数，这个很关键
                map[i][people_index+j]=1;
            }
            map[people_index+house_index][i]=1;//构建超级汇点和超级源点
            map[people_index+i][people_index+house_index+1]=1;
        }
        min_cost_max_flow(people_index+house_index+2,people_index+house_index,people_index+house_index+1);
        printf("%d\n",sum_cost);
    }
    return 0;
}