Good Transformation

Description

The transportation problem is to minimize the cost of transporting good from m source nodes to n destination nodes through arcs. Arcs are directed routes from source to destination which have no capacity limitation, but there is a cost associated with each arc for each unit of goods transported through. Each source has a supply amount, and each destination has a demand amount.

In this problem, the source nodes are numbered from 1 to m, and the destination nodes are numbered from 1 to n. There is one arc between each pair of the source node and the destination node. The cost of the arc originated from source node a (1 <= a <= m) to destination node b (1 <= b <= n) is a + b. The supply for each source nodes and the demand for each destination node are also given. You are going to calculate the maximal possible amount of goods that can be transported from source to destination, and also the minimized cost to achieve that goal.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

For each case, the numbers of source and destination nodes, m (1 <= m <= 10,000) and n (1 <= n <= 10,000), are given in the first line. The next line contains m integers, which are the supply amounts for each source, and the next line n integers, which are the demand amounts of each destination. All supply and demand amounts are non-negative numbers less than or equal to 10,000.

Output

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each test case print in one line the two integers - the maximal amount of goods that can be transported to destination, and the minimized cost for transporting those goods. Separate them with a single space.

Sample Input

1

3 4
2 5 6
4 3 1 5

Sample Output

Case 1:
13 63

算法思想以及求解步骤

思想：题目中要求解最大可运输的货物数量以及运输这些货物的最小的花费成本，因为花费成本是根据编号来计算的，因此肯定从编号最小的开始计算，先把编号小的货物运输完，然后在运输其余的。显然是贪心算法。对于求最大可运输的货物来说，就是对比需求量的和与供应量的和，看哪个小，就是最大运输货物的数量。

求解步骤：1.按要求输入源节点的供应量和目的地的需求量，保存在两个数组中，并保存供应量的和、需求量的和。

                  2.在两个for循环中，依次判断源节点的供应量与目的节点的需求量的大小，如果源节点的供应量大于目的节点的需求量，那么将源节点的供应量更新（减去需求量的值，表示已经运送了），同时计算cost（花费），然后将需求量的值赋值0，表示此节点的需要量已经满足，可以进行下一个目的节点的查看；如果源节点的供应量小于目的节点的需求量的话，直接更新目的节点的需求量（等于目的节点的需求量减去源节点的供应量），同时计算cost，并且执行break，跳出内层循环，直接从下一个源节点运输货物。

                 3.按照要求输出运输最大数量和最小花费成本。

样例的求解过程

源程序

#include<stdio.h>
int min(int a,int b)
{
	return a>b? b:a;
}
int main(){
	int a,sumx=0,sumy=0;
	int cost=0;
	scanf("%d\n",&a);
	int q=1;
	while(a--){
		int m,n;
		scanf("%d%d",&m,&n);
		int x[m+1]={0};
		int y[n+1]={0};
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&x[i]);
			sumx+=x[i];
		}
			
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&y[i]);
			sumy+=y[i];
		}
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++){
				if(x[i]==0)
					break;
				if(y[j]==0)
					continue;
				if(x[i]<=y[j])
				{
					y[j]-=x[i];
					cost+=(i+j)*(x[i]);
					break;
				}
				else{
					x[i]-=y[j];
					cost+=(i+j)*(y[j]);
					y[j]=0;
				}
			}
			if(y[n]==0)
				break;
		}
		printf("Case %d\n",q++);
		printf("%d %d",min(sumx,sumy),cost);
		
	}
	return 0;
}