ネットの流れ——最小費用の最大フロー

最小費用の最大フローを学ぶ前に、最大ストリームアルゴリズムを学ぶ必要があります.最大ストリームアルゴリズムでは、エッジの費用問題は考慮されていない.MinCostMaxFlowには、費用の概念が導入されている.cijは辺(i,j)単位の流量を表す費用である.流量=v(f)を満足させるとともに、費用が一番少ないことが要求されます.
    最小費用の最大ストリームの反復アルゴリズム:
    1.sからtまでの最小費用通路(spfa)と通路の最大流量fを求める.
    2.通路の端(i,j)の流量にfを引かせる.リバースエッジ(j,i)を追加します.容量はfで、費用は−cost(i,j)です.
    3.sからtまでの流量=v(f)またはsからtまでの最小料金道路が見つからないまで、1,2を繰り返します.
最小費用最大ストリームアルゴリズムはまた、二分図の最適整合を解決することができる.
 
最小費用の最大ストリームテンプレート:

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     
}

 
poj 2516 2195を参照してください.