当前位置:编程学习 > C/C++ >>

poj2516-经典最小费用最大流-有点难度

题目意思,这个理解起来就很费劲
       有N个供给商,M个雇主,K种物品。每个供给商对每种物品的的供给量已知,每个雇主对每种物品的需求量的已知,从不同的供给商输送不同的货物到不同的雇主手上需要不同的花费,又已知从供给商Mj送第kind种货物的单位数量到雇主Ni手上所需的单位花费。
问:供给是否满足需求?若是满足,最小运费是多少?
样例解释

算法分析
1、供给是否满足需求
      首先我们要看供给是否满足需求,要求最小费用,必须先满足供给大于等于需求才可以。我们必须求出第k种货物的总供给量和总消费量。如果有一种货物的消费量大于供给量,那么直接输出-1,不过记住要先将题目的输入读完,否则wa到死。然后只有供给大于需求,才能找出最小值,也一定能找到最小值。
2、 最小费用最大流
       从题目明显看出由于是n个人,所以死多源点多汇点的最小费用最大流。但是其实题目已经给出了提示,后面是k个N*M的矩阵,其实就是想让我们先计算每一种货物的最小费用,然后求和即可。通过分析很容易发现,这k中货物的最小费用好不想干,不会相互影响。
3、 那么如何建图呢
       源点s和汇点t,定义各点编号如下:源点s编号为0,供给商编号从1到M,雇主编号从M+1到M+N,汇点t编号为M+N+1。总结点数nmax=M+N+2,申请每条边的“花费”空间map[nMax][ nMax]和“容量”空间cap[nMax][ nMax],并初始化为全0。源点s向所有供给商M建边,费用为0,容量为供给商j的供给量。
       每个供给商都向每个雇主建边,正向弧费用为输入数据的第k个矩阵,容量为供给商j的供给量;反向弧费用为正向弧费用的负数,容量为0。
        所有雇主向汇点t建边,费用为0,容量为雇主i的需求量。     
4、算法实现
       对于第k种物品的图,用spfa算法求解最小费用路径(增广流链),在这条路径上求出流量的最小值,其实也是最大的流量,然后在路径上正向减去此流量,反向加上此流量,费用为单价乘以此流量。
 
代码:
[cpp] 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define nMax 300 
#define inf 0x7fffffff 
#define Min(a,b) (a<b?a:b) 
 
int map[nMax][nMax];//map[i][j]表示对于每种k物品从i运输到j所花费的钱 
int vis[nMax];//表示i是否用过 
int cap[nMax][nMax];//表示i到j的最大通货量 
int dis[nMax];//到i的距离 
int que[nMax];//队列 
int pre[nMax];//保存每一条最短增流路 
int num,ans;//num-最后的汇点,ans最终的答案 
 
int spfa()//spfa求最短路径,dijstra不允许有负权,所以这里使用spfa 

    int i,k; 
    int head,tail; 
    memset(vis, 0, sizeof(vis)); 
    for (i = 0; i <= num; ++ i) 
    { 
        dis[i] = inf; 
    } 
    dis[0] = 0; 
    vis[0] = 1; 
    head = tail = 0; 
    que[0] = 0; 
    tail ++; 
    while (head < tail) 
    { 
        k = que[head]; 
        vis[k] = 0; 
        for (i = 0; i <= num; ++ i) 
        { 
            if (cap[k][i] && dis[i] > dis[k] + map[k][i])//如果k到i还有量,表明还可以增流,那么就求最短路 
            { 
                dis[i] = dis[k] + map[k][i]; 
                pre[i] = k; 
                if (!vis[i]) 
                { 
                    vis[i] = 1; 
                    que[tail ++] = i; 
                } 
            } 
        } 
        head ++; 
    } 
    if (dis[num] < inf) 
    { 
        return 1; 
    } 
    return 0; 

 
void end() 

    int i, sum = inf; 
    for (i = num; i!= 0; i = pre[i])//找到可以增加的最大的流,是整条最短路上的最小流 
    { 
        sum = Min(sum, cap[pre[i]][i]); 
    } 
    for (i = num; i != 0; i = pre[i]) 
    { 
        cap[pre[i]][i] -= sum;//正向减去增加的流 
        cap[i][pre[i]] += sum;//逆向加上增加的流 
        ans += map[pre[i]][i] * sum;//计算本次的花费,实际上就是从place pre[i]到第i个人对于当前种类的物品所花费的钱 
    } 

 
int main() 

    int N,M,K,i,j,k; 
    int need[nMax][nMax]; 
    int needk[nMax]; 
    int have[nMax][nMax]; 
    int havek[nMax]; 
    int flag; 
    while (scanf("%d %d %d", &N, &M, &K), N) 
    { 
        memset(needk, 0, sizeof(needk)); 
        for (i = 1; i <= N; ++ i) 
        { 
            for (j = 1; j <= K; ++ j) 
            { 
                scanf("%d", &need[i][j]); 
                needk[j]  += need[i][j];//求出每种货物最大的需求量 
            } 
        } 
        memset(havek, 0, sizeof(havek)); 
        for (i = 1; i <= M; ++ i) 
        { 
            for (j = 1; j <= K; ++ j) 
            { 
                scanf("%d", &have[i][j]); 
&n

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,