解題區/解題區 - Zerojudge

b316. 紅圓茵可的消失

contents

  1. 1. 內容 ：
  2. 2. 輸入說明 ：
  3. 3. 輸出說明 ：
  4. 4. 範例輸入 ：
  5. 5. 範例輸出 ：
  6. 6. 提示 ：
  7. 7. Solution

內容 ：

「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你，在茵可家到處尋找，卻始終不見紅圓茵可的身影。
四處打聽之下，得知茵可前往神秘之山－「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界，只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著，「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店，這些便利商店剛好開在結界外，茵可每天都會到山下的其中一間購買民生用品，而且到哪家便利商店是可以預測的。板擦山上有N個點，每個點有各自的編號，越高的點編號越小，點跟點之間有道路連接，茵可所在的山頂為編號0的點，便利商店也是其中的一個點。茵可每天會由山頂出發，經過一些點後到山下的便利商店買東西。當茵可走到一個點x後，他會先走跟x有連接的點中，編號比x大(當然要往山下走阿)的點中，編號最小的那一個。而下一次又到x時就走第二小的，直到編號比x大的點都走過一次，就會回到最小的點繼續走。(假設 3號點連到 1,4,5，第一次到3時，茵可會走向4。下一次到3時，茵可會走向5。再下一次到3時，茵可會走向4。)若一個點沒有連到編號比它大的點，則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖，你就可以預測茵可在第K天時會走到哪一家便利商店了!

輸入說明 ：

第一行有兩個正整數N,M,K，表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資

  1. N<=10,K<=100
  2. N<=10,K<=100
  3. N<=1000,K<=1000
  4. N<=1000,K<=1000000000，整張圖為一棵樹
  5. N<=1000,K<=1000000000

輸出說明 ：

輸出第K天時茵可會走到哪個點。

範例輸入 ：

1
2
3
4
5
6
7
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4

範例輸出 ：

1
4

提示 ：

範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4

Solution

一開始曲解題目了，不過沒關係。

首先讓我們來了解多久一循環，根據公式$cycle(u) = \sum cycle(v) | u \rightarrow v$，這個很容易理解的，事實上 cycle(0) 可能很大派不上用場。

如果試圖用週期 M 天，則期望用模擬迭代到 M 天是否與第一天相同，則很容易在 M + 1 天不會與第二天相同，因為路徑相同不代表狀態相同。

藉此我們利用動態規劃的概念，來找尋狀態的基底位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int main() {
    int N, M, K;
    int x, y;
    while (scanf("%d %d %d", &N, &M, &K) == 3) {
        for (int i = 0; i < N; i++)
            g[i].clear();
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            if (x > y)	swap(x, y);
            g[x].push_back(y);
        }
        for (int i = 0; i < N; i++)
            sort(g[i].begin(), g[i].end());
        int pass[1024] = {};
        int now = 0, x, sum = 0;
        pass[0] = --K;
        for (int i = 0; i < N; i++) {
            if (g[i].size() == 0)	continue;
            int u = i, v, div = pass[u] % g[i].size();
            for (int j = 0; j < g[i].size(); j++) {
                v = g[i][j];
                pass[v] += pass[u] / g[i].size();
                if (j < div)
                    pass[v]++;
            } 
        }
        for (; g[now].size(); ) {
            x = pass[now]%g[now].size();
            now = g[now][x];
//			printf("-> %d\n", now);
        }
        printf("%d\n", now);
    }
    return 0;
}
/*
5 6 1
0 1
0 2
1 2
2 3
0 4
1 4
5 6 2
0 1
0 2
1 2
2 3
0 4
1 4
5 6 3
0 1
0 2
1 2
2 3
0 4
1 4
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
*/