算法由来：

在最大流中，我们需要做的只是不停地增广，但是增广全部结束后的残量网络并不唯一，因此不同的增广方式构成的最大流对应了不同的流量。因此，如果给最大流添加一个条件：$\sum{flow*price}$最小，那么可以 增大题目难度缩小解集范围，更有实用价值与普遍适用性。

算法一般步骤：

最小费用最大流的一般步骤是：

与最大流唯一的不同是：增广的方式是用最短路增广：即每次选取所有增广路中最短的

于是模板就是：

/*省略不重要的部分*/

int dist[MX*MX],book[MX*MX],pre[MX*MX],q[MX*MX];
int h,t,now;

bool SPFA(int *flow,int *cost)
{
    memset(dist,0x3f,sizeof(dist));
    memset(book,0,sizeof(book));
    memset(pre,0,sizeof(pre));
    memset(q,0,sizeof(q));
    h=t=1;
    q[h]=S;
    dist[S]=0;
    book[S]=1;
    pre[S]=-1;
    while(h>=t)                                                 //求最短路并记录路径
    {
        now=q[t];
        book[q[t]]=0;
        t++;
        for(int i=fst[now];i!=-1;i=nxt[i])
        {
            if(e[i].cap>0&&dist[e[i].v]>dist[now]+e[i].val)
            {
                dist[e[i].v]=dist[now]+e[i].val;
                pre[e[i].v]=i;
                if(book[e[i].v]==0)
                {
                    book[e[i].v]=1;
                    q[++h]=e[i].v;
                }
            }
        }
    }
    if(dist[T]>=INF)return 0;
    int mxfl=INF,cstd=0;
    now=pre[T];
    while(now!=-1)
    {
        mxfl=min(mxfl,e[now].cap);                              //获得最短增广路的流量
        cstd+=e[now].val;
        now=pre[e[now].u];
    }
    now=pre[T];
    while(now!=-1)
    {
        e[now].cap-=mxfl;                                       //更新残量网络
        e[now^1].cap+=mxfl;
        now=pre[e[now].u];
    }
    *flow+=mxfl;
    *cost+=mxfl*cstd;
    return 1;
}

void mincost()
{
    int flow=0,cost=0;
    while(SPFA(&flow,&cost));
    cout<<cost<<endl;
}

附上 HDU1533 Going Home 的代码，你也可以在这个博客里查看这一题的题解

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MX 200
#define S 0
#define T mnum+hnum+1

using namespace std;

int n,m;
typedef struct eges
{
    int cap,val,u,v;
} edge;
typedef struct points
{
    int x,y;
} point;
edge e[MX*MX];
point man[MX],hos[MX];
int lnum,fst[MX*MX],nxt[MX*MX];
int mnum,hnum;

point makep(int a,int b)
{
    point x;
    x.x=a,x.y=b;
    return x;
}

void init()
{
    lnum=-1;
    mnum=0;
    hnum=0;
    memset(fst,0xff,sizeof(fst));
}

int manhat(point a,point b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}

void addeg(int nu,int nv,int cap,int val)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    e[lnum].cap=cap;
    e[lnum].val=val;
    e[lnum].u=nu;
    e[lnum].v=nv;
}

void outeg(int ee)
{
    cout<<e[ee].u<<" "<<e[ee].v<<endl;
}

void input()
{
    char ch;
    scanf("%d%d",&n,&m);
    if(n==0&&m==0)exit(0);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            ch=getchar();
            while(ch!='H'&&ch!='m'&&ch!='.')ch=getchar();
            if(ch=='m')man[++mnum]=makep(i,j);
            else if(ch=='H')hos[++hnum]=makep(i,j);
        }
    }
}

void build()
{
    for(int i=1; i<=mnum; i++)
    {
        for(int j=1; j<=hnum; j++)
        {
            addeg(i,mnum+j,1,manhat(man[i],hos[j]));
            addeg(mnum+j,i,0,-manhat(man[i],hos[j]));
        }
    }
    for(int i=1; i<=mnum; i++)
    {
        addeg(S,i,1,0);
        addeg(i,S,0,0);
    }
    for(int j=1; j<=hnum; j++)
    {
        addeg(mnum+j,T,1,0);
        addeg(T,mnum+j,0,0);
    }
}

int dist[MX*MX],book[MX*MX],pre[MX*MX],q[MX*MX];
int h,t,now;

bool SPFA(int *flow,int *cost)
{
    memset(dist,0x3f,sizeof(dist));
    memset(book,0,sizeof(book));
    memset(pre,0,sizeof(pre));
    memset(q,0,sizeof(q));
    h=t=1;
    q[h]=S;
    dist[S]=0;
    book[S]=1;
    pre[S]=-1;
    while(h>=t)
    {
        now=q[t];
        book[q[t]]=0;
        t++;
        for(int i=fst[now];i!=-1;i=nxt[i])
        {
            if(e[i].cap>0&&dist[e[i].v]>dist[now]+e[i].val)
            {
                dist[e[i].v]=dist[now]+e[i].val;
                pre[e[i].v]=i;
                if(book[e[i].v]==0)
                {
                    book[e[i].v]=1;
                    q[++h]=e[i].v;
                }
            }
        }
    }
    if(dist[T]>10000)return 0;
    int mxfl=99999,cstd=0;
    now=pre[T];
    while(now!=-1)
    {
        mxfl=min(mxfl,e[now].cap);
        cstd+=e[now].val;
        now=pre[e[now].u];
    }
    now=pre[T];
    while(now!=-1)
    {
        e[now].cap-=mxfl;
        e[now^1].cap+=mxfl;
        now=pre[e[now].u];
    }
    *flow+=mxfl;
    *cost+=mxfl*cstd;
    return 1;
}

void minst()
{
    int flow=0,cost=0;
    while(SPFA(&flow,&cost));
    cout<<cost<<endl;
}

int main()
{
    while(1)
    {
        init();
        input();
        build();
        minst();
    }

    return 0;
}