费用流

最小费用最大流（转至Lost（转至威士忌）的代码）

））：

每次在s-t之间找出费用最小的一条路径即单源最短路，如果t点不再被访问到，则算法终止。否则，按着最短路径找出最小剩余容量c，最大流量加上 c，再更新最短路径上的边，前向弧减去c，反向弧加上c，并且造一条逆向的费用边，最小费用加上每条边的花销，每条边的花销=单位费用*c。

最小费用最大流既能求最小费用，又能得出最大流，是更为一般的模型。

牛人哈~~~自己也懒得看原理了,代码中使用了bellman-ford算法,貌似可以改进为spfa,会更好。

/**** **** **** **** **** ****
网络中最小费用最大流
参数含义:    n代表网络中的总节点数
            net[][]代表剩余网络
            cost[][]代表单位费用
            path[]保存增广路径
            ecost[]源点到各点的最短路
算法:初始最小费用和最大流均为，寻找单位费用最短路
在最短路中求出最大流，即为增广路，再修改剩余网络，直到无可增广路为止
返回值:        最小费用，最大流量
**** **** **** **** **** ****/ 
const int NMAX = 210;
int net[NMAX][NMAX], cost[NMAX][NMAX];
int path[NMAX], ecost[NMAX];
int n;
bool bellman_ford()
{
    int i,j;
    memset(path,-1,sizeof(path));
    fill(ecost, ecost+NMAX, INT_MAX);
    ecost[0] = 0;

    bool flag = true;
    while(flag) {
        flag = false;
        for(i=0;i<=n;i++) {
            if(ecost[i] == INT_MAX) {
                continue ;
            }
            for(j=0;j<=n;j++) {
                if(net[i][j] > 0 && ecost[i]+cost[i][j] < ecost[j]) {
                    flag = true;
                    ecost[j] = ecost[i]+cost[i][j];
                    path[j] = i;
                }
            }
        }
    }
    return ecost[n] != INT_MAX;
}

int min_cost_max_flow()
{
    int i,j;
    int mincost = 0, maxflow = 0;
    while( bellman_ford() ) {
        int now = n;
        int neck = INT_MAX;
        while(now != 0) {
            int pre = path[now];
            neck = min(neck, net[pre][now]);
            now = pre;
        }
        maxflow += neck;
        now = n;
        while(now != 0) {
            int pre = path[now];
            net[pre][now] -= neck;
            net[now][pre] += neck;
            cost[now][pre] = - cost[pre][now];
            mincost += cost[pre][now] * neck;
            now = pre;
        }
    }
    return mincost;
}

spfa+静态邻接表

/*存边的时候注意前向弧存在Edge数组的偶数里面，后向弧存在奇数里面，并且相差1*/

#include <iostream>
#include <queue>
using namespace std;

#define fmax(a,b) (a>b?a:b)
#define fmin(a,b) (a<b?a:b)
const long inf = 1e9;
const long maxn_edge = 10005;
const long maxn_point = 105;

int Index;
int n,m;
struct node
{
    int to;
    int c; //容量
    int w; //费用
    int next;
}Edge[maxn_edge];
int pre[maxn_point];
int dir[maxn_point],path_v[maxn_point],path_e[maxn_point],vis[maxn_point];//求最短路
queue<int> Q;

inline void _insert(int from,int to,int c,int w)
{
    Edge[Index].to = to;
    Edge[Index].c = c;
    Edge[Index].w = w;
    Edge[Index].next = pre[from];
    pre[from] = Index++;
}

void insert(int from,int to,int c,int w)
{
    _insert(from,to,c,w);
    _insert(to,from,0,-w);
}

int Init()
{
    //CODE
    return 1;
}
int min_cost_max_flow(int start,int end)
{
    int i;
    int min_cost = 0,max_flow = 0;
    while(true)
    {
        memset(path_v,-1,sizeof(path_v));
        memset(path_e,-1,sizeof(path_e));
        memset(vis,0,sizeof(vis));
        fill(dir,dir+maxn_point,inf);

        dir[start] = 0;
        Q.push(start);
        vis[start] = true;
        while(!Q.empty())
        {
            int x = Q.front();
            vis[x] = false;
            Q.pop();

            for(i=pre[x];(i+1);i=Edge[i].next)
            {
                int y = Edge[i].to;
                if(Edge[i].c && dir[y] > dir[x] + Edge[i].w)
                {
                    dir[y] = dir[x] + Edge[i].w;
                    if(!vis[y])
                    {
                        vis[y] = true;
                        Q.push(y);
                    }
                    path_v[y] = x,path_e[y] = i;
                }
            }
        }


        if(path_v[end] == -1) //dir[end] == inf
            break;

        int Min = inf;
        for(i=end;i!=start;i=path_v[i])
        {
            Min = fmin(Min,Edge[path_e[i]].c);
        }

        max_flow += Min;
        min_cost += Min * dir[end];

        for(i=end;i!=start;i=path_v[i])
        {
            Edge[path_e[i]].c -= Min;
            Edge[path_e[i]^1].c += Min;
        }
    }

    return min_cost;
}

int main()
{
    while(Init())
    {
        int num = min_cost_max_flow(1,n);
        printf("%d\n",num);
    }
    return 0;
}