POJ 2516 - Minimum Cost

ACM POJ 解题报告
算法
原创
发布日期:   2011-02-27
更新日期:   2026-11-06
文章字数:   2.9k
阅读时长:   13 分
阅读次数:  

0x00 POJ 原题

Description

Dearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from 1 to N) which stocks goods from him.Dearboy has M supply places (marked from 1 to M), each provides K different kinds of goods (marked from 1 to K). Once shopkeepers order goods, Dearboy should arrange which supply place provide how much amount of goods to shopkeepers to cut down the total cost of transport.

It’s known that the cost to transport one unit goods for different kinds from different supply places to different shopkeepers may be different. Given each supply places’ storage of K kinds of goods, N shopkeepers’ order of K kinds of goods and the cost to transport goods for different kinds from different supply places to different shopkeepers, you should tell how to arrange the goods supply to minimize the total cost of transport.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, K (0 < N, M, K < 50), which are described above. The next N lines give the shopkeepers’ orders, with each line containing K integers (there integers are belong to [0, 3]), which represents the amount of goods each shopkeeper needs. The next M lines give the supply places’ storage, with each line containing K integers (there integers are also belong to [0, 3]), which represents the amount of goods stored in that supply place.

Then come K integer matrices (each with the size N * M), the integer (this integer is belong to (0, 100)) at the i-th row, j-th column in the k-th matrix represents the cost to transport one unit of k-th goods from the j-th supply place to the i-th shopkeeper.

The input is terminated with three “0”s. This test case should not be processed.

Output

For each test case, if Dearboy can satisfy all the needs of all the shopkeepers, print in one line an integer, which is the minimum cost; otherwise just output “-1”.

Sample Input

1 3 3   
1 1 1
0 1 1
1 2 2
1 0 1
1 2 3
1 1 1
2 1 1

1 1 1
3
2
20

0 0 0

Sample Output

4
-1

Source

POJ Monthly–2005.07.31, Wang Yijie

0x10 题目概述

有 N 个供应商，M 个店主，K 种物品。每个供应商对每种物品的的供应量已知，每个店主对每种物品的需求量的已知，从不同的供应商运送不同的货物到不同的店主手上需要不同的花费，又已知从供应商 Mj 送第 kind 种货物的单位数量到店主 Ni 手上所需的单位花费。

问：供应是否满足需求？如果满足，最小运费是多少？

0x20 解题思路

费用流问题。

（1）输入格式：

在说解题思路之前，首先说说输入格式，因为本题的输入格式和解题时所构造的图的方向不一致，必须要提及注意。以样例 1 为例：

（2）题目分析和拆解：

0x21 首先处理“供应是否满足需求”的问题

要总供应满足总需求，就必须有 每种物品的供应总量都分别满足其需求总量，只要有其中一种物品不满足，则说明供不应求，本组数据无解，应该输出-1。但是要注意这里判断无解后，只能做一个标记，但还要继续输入，不然一旦中断输入，后面的几组数据结果就全错了。

而要知道“每种物品的供应总量都分别满足其需求总量”，对所有供应商第 kind 种物品的供应量求和 ksupp[kind]，对所有店主第 kind 种物品的需求量求和 kneed[kind]，然后比较 ksupp[kind] 与 kneed[kind] 就可以了。

而最小费用流的计算是建立在“供等于求”或“供过于求”的基础上的。

0x22 最小费用问题

要直接求出“把所有物品从所有供应商运送到所有店主的最小费用 MinTotalCost”是不容易的。但是求出“把第 kind 种物品从所有供应商运送到所有店主的最小费用 MinCost[kind]”却简单得多，这就转化为经典的多源多汇的费用流问题，而最后只需要把 K 种物品的最小费用求和 MinCost[kind]，就能得到运送所有物品的最小费用 MinTotalCost。

其实题目的输入方式最后要输入 K 个矩阵已经暗示了我们要拆解处理。

0x23 构图

那么对于第 kind 种物品如何构图呢？

解决多源多汇网络问题，必须先构造与其等价的单源单汇网络。构造超级源 s 和超级汇 t，定义各点编号如下：

超级源 s 编号为 0，供应商编号从 1 到 M，店主编号从 M+1 到 M+N，超级汇 t 编号为 M+N+1。

令总结点数 Nump=M+N+2，申请每条边的“花费”空间 cost[Nump][Nump] 和“容量”空间 cap[Nump][Nump]，并初始化为全 0。

超级源 s 向所有供应商 M 建边，费用为 0，容量为供应商 j 的供应量。

每个供应商都向每个店主建边，正向弧费用为输入数据的第 kind 个矩阵（注意方向不同），容量为供应商 j 的供应量；反向弧费用为正向弧费用的负数，容量为 0。

所有店主向超级汇 t 建边，费用为 0，容量为店主 i 的需求量。

注意：

  1. 其他没有提及的边，费用和容量均为 0，容量为 0 表示饱和边或不连通。
  2. 计算每种物品的最小费用都要重复上述工作重新构图，不过存储空间 cost 和 cap 不必释放，可重新赋值再次利用。

0x24 求解

对于第 kind 种物品的图，都用 spfa 算法求解最小费用路径（增广链），再利用可分配最大流调 MaxFlow 整增广链上的容量，正向弧容量减去 MaxFlow，反向弧容量减去 MaxFlow，费用为单位花费乘以 MaxFlow。

具体的算法流程可参考我 POJ2195 的解题报告，基本一样。但注意的导致本题无可行解的原因只有“供不应求”，由输入数据知显然各边的容量均>=0，因此并不会出现负权环，spfa 仍然用 while 循环直至无增广链为止足矣。

0x30 AC 源码

//Memory Time 
//596K  1188MS 

#include<iostream>
#include<queue>
using namespace std;

class solve
{
public:
    solve(int n,int m,int k):N(n),M(m),K(k)
    {
        MinTotalCost=0;
        Nump=N+M+2;
        s=0;
        t=N+M+1;
        Err=false;

        AppRoom();
        Input();
        Compute();
    }
    ~solve()
    {
        if(Err)
            cout<<-1<<endl;
        else
            cout<<MinTotalCost<<endl;

        Relax();
    }

    int inf() const{return 0x7FFFFFFF;}
    int min(int a,int b) {return a<b?a:b;}
    bool check(int kind) const{return ksupp[kind]>=kneed[kind];}

    void AppRoom(void);            //申请存储空间
    void Input(void);            //输入
    void Compute(void);            //计算MinTotalCost
    void Initial(int kind);        //初始化数据，重新构造第kind种物品的流量图
    bool spfa(void);            //对当前图求最小费用流(增广链)
    void AddFlow(int kind);        //对最小费用流增流，调整增广链上的流量和费用，并累计第kind种物品的费用MinCost[kind]
    void Relax(void);            //释放空间

protected:
    int N;                //店主数
    int M;                //供货商数
    int K;                //商品种数
    int s,t;            //超级源s 与 超级汇t 的编号
    int Nump;            //N+M+超级源s+超级汇t (即总结点数量)
    int** supply;        //supply[j][k]:供货商j对第k种物品的供货量
    int** need;            //need[i][k]: 店主i对第k种物品的需求量
    int*** InputCost;    //InputCost[kind][N][M] 对应输入的K的花费矩阵
    int* MinCost;        //所有供货商运送第k种货物给所有店主的最小花费
    int MinTotalCost;    //所有供货商运送所有物品给所有店主的最小总花费

    /*构图时各点编号-- 超级源s:0 , 供应商M:1~M , 店主N:M+1~M+N , 超级汇t:N+M+1*/
    int** cost;            //任意两点之间的花费
    int** cap;            //任意两点之间的容量
    int* dist;            //超级源到各点的距离
    int* vist;            //判断某点是否在队列中

    int* pre;            //记录前驱. u->v，pre[v]=u
    bool Err;            //标记供不应求
    int* ksupp;            //第k种物品的总供应量
    int* kneed;            //第k种物品的总需求量
};

void solve::AppRoom(void)
{
    int i,k;

    /*申请构图与解题必要空间*/

    MinCost=new int[K+1];
    ksupp=new int[K+1];
    kneed=new int[K+1];
    dist=new int[Nump];
    vist=new int[Nump];
    pre=new int[Nump];

    cost=new int*[Nump];
    cap=new int*[Nump];
    for(i=0;i<Nump;i++)
    {
        cost[i]=new int[Nump];
        cap[i]=new int[Nump];
    }

    /*申请输入空间*/

    supply=new int*[M+1];
    for(i=1;i<=M;i++)
        supply[i]=new int[K+1];

    need=new int*[N+1];
    for(i=1;i<=N;i++)
        need[i]=new int[K+1];

    InputCost=new int**[K+1];    //K个矩阵
    for(k=1;k<=K;k++)
    {
        InputCost[k]=new int*[N+1];
        for(i=1;i<=N;i++)
            InputCost[k][i]=new int[M+1];
    }

    return;
}

void solve::Input(void)
{
    int i,j,k;

    for(i=1;i<=N;i++)
        for(k=1;k<=K;k++)
            cin>>need[i][k];

    for(j=1;j<=M;j++)
        for(k=1;k<=K;k++)
            cin>>supply[j][k];

    for(k=1;k<=K;k++)
        for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
                cin>>InputCost[k][i][j];

    /*计算第k种物品的供应总量和需求总量*/

    for(k=1;k<=K;k++)
    {
        ksupp[k]=0;
        for(j=1;j<=M;j++)
            ksupp[k]+=supply[j][k];

        kneed[k]=0;
        for(i=1;i<=N;i++)
            kneed[k]+=need[i][k];
    }

    return;
}

void solve::Compute(void)
{
    for(int kind=1;kind<=K;kind++)
    {
        Initial(kind);
        if(!check(kind))    //检查第k种物品的供求情况
        {
            Err=true;
            return;
        }

        while(spfa())
            AddFlow(kind);

        MinTotalCost+=MinCost[kind];
    }

    return;
}

void solve::Initial(int kind)
{
    int i,j;

    MinCost[kind]=0;
    memset(pre,0,sizeof(int)*Nump);

    for(i=0;i<Nump;i++)        //目的是处理不属于当前所构造的图的边
    {
        memset(cap[i],0,sizeof(int)*Nump);
        memset(cost[i],0,sizeof(int)*Nump);
    }

    /*初始化超级源s到各个供货商的容量*/

    for(j=1;j<=M;j++)
        cap[s][j]=supply[j][kind];    //s到供货商j的容量为供货商j的供应量


    /*初始化各个店主到超级汇t的容量*/

    for(i=M+1;i<t;i++)
        cap[i][t]=need[i-M][kind];    //店主i到t的容量为店主i的需求量

    /*初始化各个供应商到各个店主的容量和费用*/

    for(i=M+1;i<t;i++)
        for(j=1;j<=M;j++)
        {
            cost[j][i]=InputCost[kind][i-M][j];    //注意这里的费用存储方式与输入的存储方式相反
            cost[i][j]=-cost[j][i];                //反向弧费用
            cap[j][i]=supply[j][kind];            //供应商j到店主i的容量为供货商j的供应量
        }

    return;
}

bool solve::spfa(void)
{
    for(int i=s;i<=t;i++)
    {
        dist[i]=inf();
        vist[i]=false;
    }
    dist[s]=0;

    queue<int>q;
    q.push(s);
    vist[s]=true;

    while(!q.empty())
    {
        int u=q.front();
        for(int v=s;v<=t;v++)
        {
            if(cap[u][v] && dist[v]>dist[u]+cost[u][v])
            {
                dist[v]=dist[u]+cost[u][v];
                pre[v]=u;

                if(!vist[v])
                {
                    q.push(v);
                    vist[v]=true;
                }
            }
        }

        q.pop();
        vist[u]=false;
    }

    if(dist[t]<inf())
        return true;        //dist[t]被修正，说明找到增广链

    return false;    //已无增广链，spfa结束
}

void solve::AddFlow(int kind)
{
    int MaxFlow=inf();        //可分配最大流
    int i;
    for(i=t;i!=s;i=pre[i])
        MaxFlow=min(MaxFlow,cap[pre[i]][i]);    //可分配最大流=增广链上的最小容量

    for(i=t;i!=s;i=pre[i])
    {
        cap[pre[i]][i]-=MaxFlow;    //正向弧容量调整
        cap[i][pre[i]]+=MaxFlow;    //反向弧容量调整
        MinCost[kind]+=cost[pre[i]][i]*MaxFlow;        //最小费用=单位费用*可分配最大流
    }

    return;
}

void solve::Relax(void)
{
    int i,k;

    delete[] MinCost;
    delete[] dist;
    delete[] vist;
    delete[] pre;
    delete[] ksupp;
    delete[] kneed;

    for(i=0;i<Nump;i++)
    {
        delete[] cost[i];
        delete[] cap[i];
    }

    for(i=1;i<=M;i++)
        delete[] supply[i];

    for(i=1;i<=N;i++)
        delete[] need[i];

    for(k=1;k<=K;k++)
    {
        for(i=1;i<=N;i++)
            delete[] InputCost[k][i];

        delete[] InputCost[k];
    }

    return;
}

int main(void)
{
    int n,m,k;
    while(cin>>n>>m>>k && (n+m+k))
        solve poj2516(n,m,k);

    return 0;
}

相关资料

文章作者: EXP
文章链接: https://exp-blog.com/algorithm/poj/poj2516-minimum-cost/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
ACM POJ 解题报告
赏
  目录