[最大流]USACO 2002 Winter Green：New Years Party 解題報告

題目鏈接：http://oj.jzxx.net/problem.php?id=1674
代碼發芽網代碼高亮：http://fayaa.com/code/view/25178/

题目描述

A group of N (3 <= N <= 200) cows is having a New Year's party. Each cow is able to cook several different kinds of food (in units called a "dish"). There are a total of D (5 <= D <= 100) different kinds of food. Each kind of food is denoted by an integer in the range 1..D. The cowrdinator wants to maximize the total number of dishes brought to the party, but has specified a limit for the number of dishes of each type. Each cow can bring K (1 <= K <= 5) dishes, but they must be different from each other (she can't bring 3 bovine pies, for example, but she could bring a pie, some bread, and some nice alfalfa in orange sauce). What is the maximum amount of food that can be brought?

USACO Dec11 Hay Bales 原題、翻譯、題解

【英文原題】
Problem 1: Hay Bales [Brian Dean, 2011]

The cows are at it again!  Farmer John has carefully arranged N (1 <= N <=
10,000) piles of hay bales, each of the same height.  When he isn't
looking, however, the cows move some of the hay bales between piles, so
their heights are no longer necessarily the same.  Given the new heights of
all the piles, please help Farmer John determine the minimum number of hay
bales he needs to move in order to restore all the piles to their original,
equal heights.

PROBLEM NAME: haybales

INPUT FORMAT:

* Line 1: The number of piles, N (1 <= N <= 10,000).

* Lines 2..1+N: Each line contains the number of hay bales in a single
        pile (an integer in the range 1...10,000).

SAMPLE INPUT (file haybales.in):

4
2
10
7
1

INPUT DETAILS:

There are 4 piles, of heights 2, 10, 7, and 1.

OUTPUT FORMAT:

* Line 1: An integer giving the minimum number of hay bales that need
        to be moved to restore the piles to having equal heights.

SAMPLE OUTPUT (file haybales.out):

7

OUTPUT DETAILS:

By moving 7 hay bales (3 from pile 2 to pile 1, 2 from pile 2 to pile 4, 2
from pile 3 to pile 4), we can make all piles have height 5.

【中文翻譯】
USACO美國信息學月賽 2011年12月賽  銅組 
Problem 1: 乾草堆

奶牛們又來了!農夫約翰成功地準備了N(1<=N<=10,000)捆乾草，每捆乾草都有相同的高度。然而，當他不注意的時候

，他的奶牛們在兩捆乾草之間移動了一部分乾草，所以這些乾草的數量不再和以前一樣了。

給你每捆乾草新的數量，請幫助農夫約翰計算出他最少需要移動多少乾草，使每捆都恢復到初始時的數量，也就是那個

相同的數量。

程序名稱：haybales

輸入格式：

*第1行：乾草的捆數N(1<=N<=10,000)。

*第2~1+N行，每行包含一個整數，表示第i捆乾草的數量，（一個1、10,000之間的整數）。

輸入樣例(file haybales.in)：

4
2
10
7
1

輸入解釋：

一共有4捆乾草，它們的高度分別是2,10,7和1。

輸出格式：

* 第一行：一個整數，表示至少需要移動多少乾草，
才能使每捆乾草恢復到相等的高度。

輸出樣例(file haybales.out)：

7

輸出解釋：
移動7份乾草（把3份乾草從第2捆移至第一捆，把2份乾草從第2捆移至第4捆，把2份乾草從第3捆移至第4捆），我們就

可以把每捆乾草的高度都變成5。
 【分析】
 貪心就可以了，也是【NOIP2002提高組 均分紙牌】的這種類型。
先統計出平均數，再計算出 每捆乾草數量與平均數的差值（的絕對值）之和，然後除以2即可。

時間複雜度：O(N*2)
空間複雜度：N

【我的代碼】

1	/*
2	ID:yeefan
3	LANG:C++
4	PROB:haybales
5	*/
6	#include <iostream>
7	#include <cstdio>
8	#include <cstdlib>
9	using namespace std;
10	int N;
11	int A[10001];
12	long long Sum=0;
13	long long Avg=0;
14
15	int abs(int x)
16	{
17	if(x<0)
18	x=-x;
19	return x;
20	}
21
22	void init()
23	{
24	scanf("%d\n",&N);
25	for (int i=1;i<=N;i++)
26	{
27	scanf("%d\n",&A[i]);
28	Avg+=A[i];
29	}
30	Avg/=N;
31	}
32
33	void work()
34	{
35	for (int i=1;i<=N;i++)
36	{
37	Sum+=abs(A[i]-Avg);
38	}
39	cout<<Sum/2<<endl;
40	}
41
42	int main()
43	{
44	freopen("haybales.in","r",stdin);
45	freopen("haybales.out","w",stdout);
46	init();
47	work();
48	return 0;
49	}

[圖論]OI練習題:商人的宣傳 merchant 解題報告

題目連結：http://cogs.yeefanblog.tk/t/441

【問題描述】


Bruce是K國的商人，他在A州成立了自己的公司，這次他的公司生產出了一批性能很好的產品，準備宣傳活動開始後的第L天到達B州進行新品拍賣，期間Bruce打算將產品拿到各個州去做推銷宣傳，以增加其影響力。
K國有很多個州，每個州都與其他一些州相鄰，但是K國對商人作宣傳卻有一些很奇怪的規定：
(1)商人只能從某些州到達另外一些州，即連通路綫是單向的，而且有些州可能是到達不了的。
(2)商人不允許在同一個州連續宣傳兩天或以上，每天宣傳完必須離開該州。
(3)商人可以多次來到同一個州進行宣傳。
Bruce想：“我必須找出一條影響力最大的路綫才行，但首先必須知道到底有多少這種符合規定的宣傳路綫可供我選擇。”現在Bruce把任務交給了你，並且出於考慮以後的需要，你還要幫他算出給出的兩州之間的路綫的總數。
【輸入格式】
輸入格式(輸入文件名merchant.in)
輸入文件第1行包含3個整數n，m，L(1≤n，L≤100)，分別表示K國的州數、連通路綫的數量，以及多少天后必須到達B州。
接下來有m行，每行一對整數五)，(1≤x,y≤n)，表示商人能從x州到達y州。
第m+2行爲一個整數q(1≤q≤100)，表示Bruce有q個詢問。
下面q行每行兩個整數A，B(1≤A，B≤n)，即A、B州的位置。

【輸出格式】
輸出格式(輸出文件名merchant.out)
輸出文件包含q行，每行一個整數t，爲所求的從A州到B州滿足上述規定的路綫總數。
輸入數據中的詢問將保證答案f在長整數範圍內，即i<2^31。

【輸入輸出樣例】
輸入(merchant.in)
4 5 6
1 2
2 3
3 4
4 1
2 4
2
1 4
4 2
輸出(merchant.out)
2
1

[分析]

這種題型我也不知道怎麽去描述，貌似是圖論中的DP~~我用了Floyd的框架寫的。Floyd算法其實就是動態規劃。因爲需要L天的宣傳，所以需要執行“Floyd 變形算法” L-1次。


我的程序的時間複雜度：O(L*n^3)

[我的代碼]

C++语言: Codee#25159

01 /*
02 *Prob:商人的宣傳(http://cogs.yeefanblog.tk/t/441)
03 *Author:Yee-fan Zhu(http://www.yeefanblog.tk/)
04 */
05 #include <iostream>
06 #include <cstdio>
07 #include <cstdlib>
08 using namespace std;
09
10 const int MAXN=101;
11 int Temp[MAXN][MAXN];
12 int Result[MAXN][MAXN];
13 int Start[MAXN][MAXN];
14
15 int N,M,L;
16
17 void init()
18 {
19     scanf("%d %d %d\n",&N,&M,&L);
20    
21     for (int i=1;i<=N;i++)
22         for (int j=1;j<=N;j++)
23             Temp[i][j]=0,
24             Result[i][j]=0,
25             Start[i][j]=0;
26    
27     for (int i=1;i<=M;i++)
28     {
29         int x,y;
30         scanf("%d %d\n",&x,&y);
31         Start[x][y]++;
32         Result[x][y]++;
33     }
34 }
35
36 void work()
37 {
38     for (int m=1;m<=L-1;m++)
39     {
40         for (int i=1;i<=N;i++)
41             for (int j=1;j<=N;j++)
42                 Temp[i][j]=Result[i][j],Result[i][j]=0;
43        
44         for (int i=1;i<=N;i++)
45             for (int j=1;j<=N;j++)
46                 for (int k=1;k<=N;k++)
47                     Result[i][j]+=Temp[i][k]*Start[k][j];
48     }
49    
50     int Q,x,y;
51     scanf("%d\n",&Q);
52     for(int i=1;i<=Q;i++)
53     {     
54         scanf("%d %d\n",&x,&y);
55         printf("%d\n",Result[x][y]);
56     }
57 }
58
59 int main()
60 {
61     freopen("merchant.in","r",stdin);
62     freopen("merchant.out","w",stdout);
63     init();
64     work();
65     return 0;
66 }