学步园

一、最小费用最大流的模型
在保证流量最大的前提下，所需的费用最小，这就是最小费用最大流问题．

带有费用的网络流图： G=（V，E，C，W）
V：顶点； E：弧；C：弧的容量；W：单位流量费用。
任意的弧<i,j>对应非负的容量c[i，j]和单位流量费用w[i，j]。满足：
① 流量f是G的最大流。
② 在f是G的最大流的前提下，流的费用最小。

F是G的最大流的集合（最大流不止一个）：

在最大流中寻找一个费用最小的流 f．

二、最小费用最大流的算法
基本思路：
   
把弧<i,j>的单位费用w[i,j]看作弧<i,j>的路径长度，每次找从源点s到汇点t长度最短（费用最小）的可增广路径进行增广。

1. 最小费用可增广路
2. 路径s到t的长度即单位流量的费用。

ps：是网络流EK算法的改进，在求增广路径的时候，把bfs改为带权的spfa，每次求权值最小的增广路。

ps：要注意一点，逆边cost[i][j] =
-cost[j][i]，不能忘了加上去。

自己的模板：邻接表。

#include<iostream>
using namespace std;

struct{
    int v, cap,
cost, next,
re;    // 
re记录逆边的下标。
}edge[eMax];
int n, m, ans;
int k, edgeHead[nMax];
int que[nMax], pre[nMax], dis[nMax];
bool vis[nMax];

void addEdge(int u, int v, int ca, int co){
    edge[k].v =
v;
    edge[k].cap
= ca;
    edge[k].cost
= co;
    edge[k].next
= edgeHead[u];
    edge[k].re =
k + 1;
    edgeHead[u]
= k ++;
    edge[k].v =
u;
    edge[k].cap
= 0;
    edge[k].cost
= -co;
    edge[k].next
= edgeHead[v];
    edge[k].re =
k - 1;
    edgeHead[v]
= k ++;
}

bool
spfa(){                  // 
源点为0，汇点为n。
    int
i, head = 0, tail = 1;
    for(i = 0; i
<= n; i ++){
       
dis[i] = inf;
       
vis[i] = false;
    }
    dis[0] =
0;
    que[0] =
0;

    vis[u] =
true;
    while(tail
>
head){       // 
这里最好用队列，有广搜的意思，堆栈像深搜。
       
int u = que[head ++];

        for(i
= edgeHead[u]; i != 0; i = edge[i].next){
           
int v = edge[i].v;
           
if(edge[i].cap && dis[v]
> dis[u] + edge[i].cost){
               
dis[v] = dis[u] + edge[i].cost;
               
pre[v] = i;
               
if(!vis[v]){
                   
vis[v] = true;
                   
que[tail ++] = v;
               
}
           
}
       
}
       
vis[u] = false;
    }
    if(dis[n] ==
inf) return false;
    return
true;
}

void end(){
    int u, p,
sum = inf;
    for(u = n; u
!= 0; u = edge[edge[p].re].v){
       
p = pre[u];
       
sum = min(sum, edge[p].cap);
    }
    for(u = n; u
!= 0; u = edge[edge[p].re].v){
       
p = pre[u];
       
edge[p].cap -= sum;
       
edge[edge[p].re].cap += sum;
       
ans += sum *
edge[p].cost;    
//  cost记录的为单位流量费用，必须得乘以流量。
    }
}

int main(){

    ...

    ans =
0;
   
while(spfa()) end();
    ...

    return
0;
}

自己的模板：邻接矩阵。

#include<iostream>
using namespace std;

int n, ans;
int cap[Max][Max], pre[Max];
int cost[Max][Max], dis[Max];
int que[Max];
bool vis[Max];

bool
spfa(){                
 //  源点为0，汇点为n。
    int i, head
= 0, tail = 1;
    for(i = 0; i
<= n; i ++){
       
dis[i] = inf;
       
vis[i] = false;
    }
    dis[0] =
0;
    que[0] =
0;

    vis[u] =
true;

    while(tail
!=
head){     
//  循环队列。
       
int u = que[head];

        for(i
= 0; i <= n; i ++)
           
if(cap[u][i] && dis[i]
> dis[u] +
cost[u][i]){  
 //  存在路径，且权值变小。
               
dis[i] = dis[u] + cost[u][i];
               
pre[i] = u;
               
if(!vis[i]){
                   
vis[i] = true;
                   
que[tail ++] = i;
                   
if(tail == Max) tail = 0;
               
}
           
}
       
vis[u] = false;
       
head ++;
       
if(head == Max) head = 0;
    }
    if(dis[n] ==
inf) return false;
    return
true;
}

void end(){
    int i, sum =
inf;
    for(i = n; i
!= 0; i = pre[i])
       
sum = min(sum, cap[pre[i]][i]);
    for(i = n; i
!= 0; i = pre[i]){
       
cap[pre[i]][i] -= sum;
       
cap[i][pre[i]] += sum;
       
ans += cost[pre[i]][i] * sum;  
//  cost[][]记录的为单位流量费用，必须得乘以流量。
    }
}

int main(){
    ....
    ans =
0;
   
while(spfa()) end();
    ....
    return
0;
}