网络流之——最小费用最大流

    学习最小费用最大流前，需要学习最大流算法。在最大流算法中，没有考虑边的费用问题。在MinCostMaxFlow中，引入了费用的概念：cij表示边(i,j)单位流量的费用。在满足流量=v(f)的同时，并且要求费用最少。

    最小费用最大流的迭代算法：

    1.求出从s到t的最小费用通路(spfa)和通路的最大流量f。

    2.让通路上的边(i,j)流量减去f；添加反向边(j,i)，容量为f，费用为-cost(i,j)。

    3.重复1,2，直到从s到t的流量=v(f)或者再也找不到从s到t的最小费用道路为止。

最小费用最大流算法还可以解决二分图最优匹配。

 

最小费用最大流模板：

const int size = 1102;
const int INF = 0x7fffffff;
struct Edge
{
	int to;
	int vol;
	int cost;
	int next;
}e[size*40];
int index[size];
int edgeNum;
int pre[size], pos[size];
int dis[size], que[size*10];
bool vis[size];

void insert(int from, int to, int vol, int cost)
{
	e[edgeNum].to = to;
	e[edgeNum].vol = vol;
    e[edgeNum].cost = cost;
	e[edgeNum].next = index[from];
	index[from] = edgeNum++;
	e[edgeNum].to = from;
	e[edgeNum].vol = 0;
    e[edgeNum].cost = -cost;
	e[edgeNum].next = index[to];
	index[to] = edgeNum++;
}

bool spfa(int s, int t)
{
	int i;
    memset(pre, -1, sizeof(pre));
	memset(vis, 0, sizeof(vis));
    int head, tail; head = tail = 0;
    for(i = 0; i < size; i++)
		dis[i] = INF;
    que[tail++] = s;
	pre[s] = s;
	dis[s] = 0;
	vis[s] = 1;
    while(head != tail)
    {
        int now = que[head++];
		vis[now] = 0;
		for(i = index[now]; i != -1; i = e[i].next)
		{
			int adj = e[i].to;
			if(e[i].vol > 0 && dis[now] + e[i].cost < dis[adj])
			{
				dis[adj] = dis[now] + e[i].cost;
				pre[adj] = now;
				pos[adj] = i;
				if(!vis[adj])
				{
					vis[adj] = 1;
					que[tail++] = adj;
				}
			}
		}
    }
    return pre[t] != -1;
}

int MinCostFlow(int s, int t, int flow)
{
	int i;
    int cost = 0;
    flow = 0;
    while(spfa(s, t))
    {
        int f = INF;
        for(i = t; i != s; i = pre[i])
            if (e[pos[i]].vol < f) f = e[pos[i]].vol;
        flow += f; cost += dis[t] * f;
        for(i = t; i != s; i = pre[i])
        {
            e[pos[i]].vol -= f;
            e[pos[i] ^ 1].vol += f;
        }
    }
    return cost; // flow是最大流值
}

 

参见poj2516 2195 2135。