poj2516Minimum Cost

Minimum Cost

Time Limit: 4000MS   Memory Limit: 65536K
Total Submissions: 14275   Accepted: 4895

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

额……被坑了。。。

啊。。。别人的题解

转载请注明出处:優YoU 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不必释放,可重新赋值再次利用。

判断无解的时候,我是这样的,反正跑出的是最大流。。。看最大流是不是满的不就好了。。。

虽然比直接扫慢。。。但是很优雅不是嘛。。。。

我的代码:

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
int head[110],tail;
struct Edge
{
	int from,to,cap,flow,cost,next;
}edge[10000000];
void add(int from,int to,int cap,int flow,int cost)
{
	edge[tail].from=from;
	edge[tail].to=to;
	edge[tail].cap=cap;
	edge[tail].flow=flow;
	edge[tail].cost=cost;
	edge[tail].next=head[from];
	head[from]=tail++;
}
int dis[110],p[110],re[110],ed;
bool iq[110];
bool bf(int &flow,int &cost)
{
	fill(dis,dis+ed+1,INT_MAX);
	memset(iq,0,sizeof(iq));
	dis[0]=0;
	iq[0]=1;
	re[0]=INT_MAX;
	queue<int>qq;
	qq.push(0);
	while(qq.size())
	{
		int from=qq.front();
		qq.pop();
		iq[from]=0;
		for(int i=head[from];i!=-1;i=edge[i].next)
		{
			Edge &e=edge[i];
			if(e.cap>e.flow&&dis[e.to]>dis[from]+e.cost)
			{
				dis[e.to]=dis[from]+e.cost;
				p[e.to]=i;
				re[e.to]=min(re[from],e.cap-e.flow);
				if(!iq[e.to])
				{
					qq.push(e.to);
					iq[e.to]=1;
				}
			}
		}
	}
	if(dis[ed]==INT_MAX)
		return 0;
	flow+=re[ed];
	cost+=dis[ed]*re[ed];
	int t=ed;
	while(t!=0)
	{
		edge[p[t]].flow+=re[ed];
		edge[p[t]^1].flow-=re[ed];
		t=edge[p[t]].from;
	}
	return 1;
}
int mincost(int goal)
{
	int flow=0,cost=0;
	while(bf(flow,cost));
	if(flow!=goal)
		return -1;
	return cost;
}
int a[60][60],b[60][60],c[60][60][60];
int main()
{
	int n,m,k;
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
		if(n==0&&m==0&&k==0)
			return 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=k;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=k;j++)
				scanf("%d",&b[i][j]);
		for(int i=1;i<=k;i++)
			for(int j=1;j<=n;j++)
				for(int ii=1;ii<=m;ii++)
					scanf("%d",&c[i][j][ii]);
		ed=n+m+1;
		int ans=0;
		for(int i=1;i<=k;i++)
		{
			tail=0;
			memset(head,-1,sizeof(head));
			for(int ii=1;ii<=m;ii++)
			{
				add(0,ii,b[ii][i],0,0);
				add(ii,0,0,0,0);
				for(int jj=1;jj<=n;jj++)
				{
					add(ii,m+jj,b[ii][i],0,c[i][jj][ii]);
					add(m+jj,ii,0,0,-c[i][jj][ii]);
				}
			}
			int goal=0;
			for(int ii=1;ii<=n;ii++)
			{
				goal+=a[ii][i];
				add(m+ii,ed,a[ii][i],0,0);
				add(ed,m+ii,0,0,0);
			}
			int t=mincost(goal);
			if(t==-1)
			{
				ans=-1;
				break;
			}
			ans+=t;
		}
		printf("%d\n",ans);
	}
}
时间: 03-31

poj2516Minimum Cost的相关文章

POJ--2516--Minimum Cost【最小费用最大流】

链接:http://poj.org/problem?id=2516 题意:有k种货物,n个客户对每种货物有一定需求量,有m个仓库,每个仓库里有一定数量的k种货物,然后k个n*m的矩阵,告诉从各个仓库到各个客户位置运送单位第k种货物所需的运费,问满足所有客户需求的最小费用,如满足不了所有客户,则输出-1. 思路:题目有点绕,不过多看看也就理解了.这道题算是最小费用最大流的入门题吧,建图很容易能想到,主要是存在k种货物,每条货物都要建一条路,同时处理起来不好写,而且路径也较多,不过可以对每种货物分开

UVA 1048 - Low Cost Air Travel(最短路)

UVA 1048 - Low Cost Air Travel 题目链接 题意:给定一些联票,在给定一些行程,要求这些行程的最小代价 思路:最短路,一张联票对应几个城市就拆成多少条边,结点表示的是当前完成形成i,在城市j的状态,这样去进行最短路,注意这题有坑点,就是城市编号可能很大,所以进行各种hash 代码: #include <cstdio> #include <cstring> #include <vector> #include <queue> #in

UVa 12587 Reduce the Maintenance Cost(Tarjan + 二分 + DFS)

题意:n个城市(n <= 10000), 有m条边(m <= 40000),每一个城市有一个维护费用Cost(i),除此之外,每条边的维修费用为去掉该边后不能通信的城市对数与边权的积.这个费用要加到这条边的两端城市的某一个,问你全部城市的最大费用的最小值.. 思路:首先边的费用能够通过Tarjan求桥之后求得(利用桥的性质),然后就是二分答案了!对于每一个点,假设有个儿子不能维护.那么不可行,否则.试着让儿子去维护边权,假设不可行,仅仅能让父亲承担. #include <iostream

手势跟踪论文学习:Realtime and Robust Hand Tracking from Depth(三)Cost Function

iker原创.转载请标明出处:http://blog.csdn.net/ikerpeng/article/details/39050619 Realtime and Robust Hand Tracking from Depth中的Cost Function 学习 首先,我们应该知道,输入的数据是什么:3D 点云数据. 3D点云给我的感觉应该是这种 输出的是:拟合好的手模型(48球体模型). 而这里的的3D 点云数据用p表示,每个球体用Sx 表示. Ci 第i个球体的中心:D表示深度图( 区分还

K-means: optimization objective(最小化cost function来求相应的参数)

类似于linear regression,K-means算法也optimization objective或者是试图使cost function求最小值. 了解K-means算法的optimization objective有助于我们(1)调试算法时,看算法是否运行正确(在本节中可以看到)(2)使算法找到更好的cluster,避免局部最优解(在下节中会讲) K-means optimization objective uc(i):表示x(i)分给的那个cluster的cluster centro

H - Minimum Cost

#include<iostream> #include<stdio.h> #include<vector> #include<string.h> #include<queue> using namespace std; const int maxn=1024; const int INF=0x3f3f3f3f; struct Edge{ int from,to,cap,flow,cost; Edge(int u,int v,int c,int f

微软第四题 给定cost能遍历的最大城市数

有向图中N*N矩阵 cost:M, 最多可以遍历的结点个数 例如A可以有0->1->2->0->1 代价:2+2+3+2=9<10 输出4 #include <iostream> using namespace std; int main(){ int N=3;int M=10; int A[][3]={{0,2,3},{4,0,2},{3,4,0}}; int last_step[3]; int dist[3][3]; for(int i=0;i<N;i+

Convolutional Neural Networks at Constrained Time Cost(精读)

一.文献名字和作者 Convolutional Neural Networks at Constrained Time Cost,CVPR 2015 二.阅读时间 2015年6月30日 三.文献的目的 作者希望在保持计算复杂度的前提下,通过修改模型深度和卷积模板的参数来提高CNN的准确率.作者通过大量的实验来找到网络结构中不同的参数的重要性,并在ImageNet2012数据集上面取得有竞争力的效果. 四.文献的贡献点 作者的贡献主要在于通过各种对比实验来说明不同的参数对于准确率的影响.理论方面的

POJ训练计划2516_Minimum Cost(网络流/费用流)

解题报告 题意: 有n个商店,m个提供商,k种商品</span> n*k的矩阵,表示每个商店需要每个商品的数目: m*k矩阵,表示每个提供商拥有每个商品的个数 然后对于每个物品k,都有n*m的矩阵 i行j列表示 从j提供商向i商店运送一个k商品的代价是多少 判断所有的仓库能否满足所有客户的需求,如果可以,求出最少的运输总费用 思路: 建图的题,不能直接把所有信息建成图,因为n和m跟k都有关系,如果那样子建图的话,就要把k种拆成m类,每个仓库连向该仓库的第k种,然后再和n连线,有费用, 不过这样