Goods Transportation
http://acm.zju.edu.cn/show_problem.php?pid=2541
Time limit: 1 Seconds
Memory limit: 32768K
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.
1. 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.
2. 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.
3. Sample Input
3 3 4 2 5 6 4 3 1 5 1 1 3 7 3 2 1 1 1 1 1
4. Sample Output
Case 1: 13 63 Case 2: 3 6 Case 3: 2 6
1 //2007-01-10 21:41:40 Accepted 2541 C++ 00:00.05 920K
2 //writen by 曹高挺
3 //尽量从ID小的源发货，尽量运往ID小的目的地
4 #include <iostream>
5 using namespace std;
6
7 int src[10000];
8 int dest[10000];
9
10 int main(){
11 int T, k;
12 int nSource, nDest;
13 long long nTotal;
14 long long nCost;
15 int i, j, tem;
16 bool bb = false;
17 scanf("%d", &T);
18 for(k=1; k<=T; k++){
19 if(bb==false) bb=true;
20 else printf("\n");
21
22 scanf("%d %d", &nSource, &nDest);
23 for(i=0; i<nSource; i++){
24 scanf("%d", &tem);
25 src[i] = tem;
26 }
27 for(i=0; i<nDest; i++){
28 scanf("%d", &tem);
29 dest[i] = tem;
30 }
31
32 nTotal = 0;
33 nCost = 0;
34 i = j = 0;
35 while(i<nSource && j<nDest){
36 tem = src[i]<dest[j]?src[i]:dest[j];
37 src[i] -= tem;
38 dest[j] -= tem;
39 nTotal += tem;
40 nCost += (i+j+2)*tem;
41 while( i<nSource && !src[i] ) i++;
42 while( j<nDest && !dest[j] ) j++;
43 }
44 printf("Case %d:\n", k);
45
46 //听说printf输出64位整型会有问题，果然如此
47 //改成cout就AC了
48 cout<<nTotal<<" "<<nCost<<endl;
49 }
50 return 1;
51 }
1 /*贪婪法，Time Limit Exceeded
2 written by czk*/
3 #include <stdio.h>
4
5 int main() {
6 int t;
7 scanf("%d", &t);
8 int src[10000];
9 int dst[10000];
10 for(int j = 0; j < t; j++) {
11 int m, n;
12 scanf("%d%d", &m, &n);
13 for(int i = 0; i < m; i++)
14 scanf("%d", &src[i]);
15 for(int i = 0; i < n; i++)
16 scanf("%d", &dst[i]);
17 int total_good = 0;
18 int total_cost = 0;
19 int upper_i = m+n;
20 for(int i = 2; i <= upper_i; i++) {
21 int total_i = 0;
22 int upper_k = (m < i-1)?m:i-1;
23 for(int k = (i-n>1)?i-n:1; k <= upper_k; k++) {
24 int goods = (src[k-1]<dst[i-k-1])?src[k-1]:dst[i-k-1];
25 if(goods == 0) continue;
26 src[k-1] -= goods;
27 dst[i-k-1] -= goods;
28 total_i += goods;
29 }
30 total_good += total_i;
31 total_cost += total_i * i;
32 }
33 printf("Case %d:\n", j+1);
34 printf("%d %d\n", total_good, total_cost);
35 if(j != t-1)
36 putchar('\n');
37 }
38 }