poj 2516 Minimum Cost (最小费用最大流)

本文主要是介绍poj 2516 Minimum Cost (最小费用最大流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=2516

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

Sample Output

4
-1

以下解说摘抄自http://blog.csdn.net/lyy289065406/article/details/6742534

比较详细易懂的讲解

基本题意

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

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

解题思路：

费用流问题。

（1）输入格式

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

（2）题目分析和拆解：

A、首先处理“供应是否满足需求”的问题。

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

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

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

B、最小费用问题

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

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

C、构图

那么对于第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不必释放，可重新赋值再次利用。

D、求解

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

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

下面是自己根据题意写的代码，初次做最小费用最大流，能写出来感觉~，，关于多源多汇的题就这样去思考建图就可以了

不过在超时无数次后找出了bug 原来是在通过源点到各个仓库的路径和各个用户到汇点的路径的费用上要对双向弧都赋值为0，否则就是超时

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
#define N 205using namespace std;
int n,m,k;
int c[N][N];
int r[N][N];int S,T;
int sum;int dist[N],vis[N],pre[N];bool spfa(int s,int t)
{queue<int >q;while(!q.empty())q.pop();for(int i=0; i<=t; i++){dist[i]=INF;vis[i]=0;//pre[i]=-1;}dist[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0; i<=t; i++){if(c[u][i]&&dist[i]>dist[u]+r[u][i]){dist[i]=dist[u]+r[u][i];pre[i]=u;if(!vis[i]){vis[i]=1;q.push(i);}}}}if(dist[T]!=INF)return true;return false;
}
void mimx()
{while(spfa(S,T)){int mi=INF;for(int i=T; i!=0; i=pre[i]){mi=min(mi,c[pre[i]][i]);}for(int i=T; i!=0; i=pre[i]){c[pre[i]][i]-=mi;c[i][pre[i]]+=mi;sum+=r[pre[i]][i]*mi;}}
}
int main()
{while(scanf("%d%d%d",&n,&m,&k)&&n){int usesum[N];int storesum[N];int use[N][55];///用户的需求int store[N][55];///仓库供应//if(n==0&&m==0&&k==0)break;sum=0;int x;///输入变量费用int flag=1;///供大于求memset(usesum,0,sizeof(usesum));for(int i=1; i<=n; i++){for(int j=1; j<=k; j++){scanf("%d",&use[i][j]);usesum[j]+=use[i][j];}}memset(storesum,0,sizeof(storesum));for(int i=1; i<=m; i++){for(int j=1; j<=k; j++){scanf("%d",&store[i][j]);storesum[j]+=store[i][j];}}for(int j=1; j<=k; j++){if(usesum[j]>storesum[j]){flag=0;break;}}if(flag==0){for(int i=1; i<=k; i++){for(int j=1; j<=n; j++){for(int h=1; h<=m; h++){scanf("%d",&x);}}}printf("-1\n");continue;}else{S=0;T=n+m+1;//memset(r,0,sizeof(r));for(int h=1; h<=k; h++){memset(c,0,sizeof(c));for(int i=1; i<=m; i++){c[S][i]=store[i][h];r[i][S]=r[S][i]=0;}for(int i=1; i<=n; i++){c[i+m][T]=use[i][h];r[T][i+m]=r[i+m][T]=0;}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){scanf("%d",&x);c[j][i+m]=store[j][h];r[j][i+m]=x;r[i+m][j]=-x;}}mimx();}printf("%d\n",sum);}}return 0;
}

这篇关于poj 2516 Minimum Cost (最小费用最大流)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！