Minimum Cost-最小费用最大流

update@2011-09-19

///主要代码
#define MAX 60
#define INF 10000000
int need[MAX][MAX];//某个shopkeeper需要的
int supply[MAX][MAX];//某个供货点各商品的存储量
int cost[MAX][MAX][MAX];//cost[k][i][j] 从j运送第k种商品到j
int graph[MAX*3+1][MAX*2+1];
int head[MAX*3+1],count;
int pre_of[MAX*3+1];// edge(pre_of[i],i)
int N,M,K;
struct node{
    int u,v,w,next;
}edge[MAX*MAX*10];

void add(int u,int v,int w){
    edge[count].u = u;edge[count].v = v;edge[count].w = w;
    edge[count].next = head[u];head[u] = count++;
}
int dist[MAX*2+1];
int SPFA(int k,int source,int sink){

    for(int i = source; i <= sink;i++){
        dist[i] = INF;
    }dist[source] = 0;

    memset(pre_of,-1,sizeof(pre_of));
    bool in_queue[MAX*2+1] = {};//初始化为不在队列中
    queue<int> my;my.push(source); in_queue[source] = true;

    while(!my.empty()){
        int start = my.front(); my.pop(); in_queue[start] = false;

        for(int i = head[start]; i!= -1;i = edge[i].next){
            int u = edge[i].u, v = edge[i].v ,w = edge[i].w;
            if(graph[u][v] > 0 && dist[v] > dist[u] + w){
                //printf("relax %d %d\n",u,v);
                dist[v] = dist[u] + w; pre_of[v] = u;
                if(!in_queue[v]){
                    in_queue[v] = true;my.push(v);
                }
            }
        }
    }
    return dist[sink] < INF;
}
bool isOk(int sink){
    int s = M+1;//每个商店
    for(int i = s;i < sink;i++){
        if(graph[i][sink] != 0)return false;
    }
    return true;
}
int minCost_maxFlow(int kind,int source,int sink){
    //把每条边的费用权值作为边长
    //每次求最短增广路径进行增流 直到找不到增广路径
    int sum = 0;
    while(SPFA(kind,source,sink)){
        //增流
        int min_flow = INF;
        for(int  i = sink;i != source;i = pre_of[i]){
            if(graph[pre_of[i]][i] < min_flow)
                min_flow = graph[pre_of[i]][i];
        }
        sum += dist[sink]*min_flow;
        for(int  i = sink; i != source;i = pre_of[i]){
            int u = pre_of[i], v = i;
            graph[u][v] -= min_flow;
            graph[v][u] += min_flow;
        }
    }
    if(!isOk(sink))return -1;
    return sum;
}
int main(){
    while(scanf("%d%d%d",&N,&M,&K) && N != 0){
        ///init

        for(int  i = 1;i <= N;i++){
            for(int j = 1;j <= K;j++)
                scanf("%d",&need[i][j]);
        }
        for(int  i = 1;i <= M;i++){
            for(int j = 1;j <= K;j++)
                scanf("%d",&supply[i][j]);
        }
        for(int k = 1;k <= K;k++){//第i种商品
            for(int i = 1;i <= N;i++){
                for(int j = 1;j <= M;j++){
                    scanf("%d",&cost[k][i][j]);//j供应给i
                }
            }
        }
        int total = 0;bool flag = true;
        for(int k = 1;k <= K && flag;k++){//第i种商品
            //供应商是 1 到 m,之后是m+1到m+n
            count = 0;memset(head,-1,sizeof(head));memset(graph,0,sizeof(graph));

            for(int i = 1;i <= M;i++){//供应商
                for(int j = 1;j <= N;j++){//商店
                    graph[i][j+M] = INF;
                    add(i,j+M,cost[k][j][i]);
                    add(j+M,i,-cost[k][j][i]);
                }
            }
            int source = 0,sink = M+N+1;

            for(int t = 1;t <= M;t++){
                graph[source][t] = supply[t][k];//从源点到某个供货点的流量表示供应
                add(source,t,0);//从源点到每个供应点的距离
            }
            for(int t = 1;t <= N;t++){
                graph[t+M][sink] = need[t][k];//第t个shopkeeper被供应的总量
                add(t+M,sink,0);//从每个商店到汇点
            }
            int t = minCost_maxFlow(k,source,sink);
            if(t == -1){printf("-1\n");flag = false;}
            else total += t;
        }
        if(flag)printf("%d\n",total);
    }
    return 0;
}




题目链接:Minimum Cost
其实求最小费用最大流的思想很简单,就是每次选取最短增广路径(路径长度为单位流量的花费),然后计算这条路径中的最大可增的流量 进行增流.刚学SPFA所以就用SPFA写的,而且把费用图和流量图分开了。SPFA用的邻接表,所以加边的时候要加负边 否则不能回流。