[圖論]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 }