Problem Solving►UVa

UVa 988 - Many Paths, One Destination

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

一個事件會走向不同的事件，如果此事件沒有其他事件可以選，則代表死亡，從第 0 個事件開始(出生)。
請求出從出生到死亡，有幾種不同的事件發生順序？

Solution

做拓撲排序，並且在每次更新被指向的數量 Ref[] 時，順便做 DP 。
如果此點已沒有被任何邊指著， 那麼到此點的方法就不會再變了。假設為 A 點，那麼到 A 點的方法總共有 dp[A] ，接著更新從 A 指出去的點(假設為 K 點)，此時到 K 點的方法則增加 dp[A] 。

最後再把所有到死亡事件的方法數相加起來即為答案。

Code

UVa 988UVa 988 - Many Paths, One Destination
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define N 100
using namespace std;

int death[N];
int Ref[N];
vector<int> v[N];
int topo(int count);
int main()
{
    bool first = true;
    int event;
    while (scanf("%d", &event) != EOF)
    {
        int n, i, j, k;
        int count = 0;
        //init
        fill(death, death + event, 0);
        fill(Ref, Ref + event, 0);
        for (i = 0; i < event; i++)
            v[i].clear();

        for (i = 0; i < event; i++)
        {
            scanf("%d", &n);
            if (!n)
                death[count++] = i;//死亡
            else
                for (j = 0; j < n; j++)
                {
                scanf("%d", &k);
                v[i].push_back(k);
                Ref[k]++;//有多少指向 K 的邊
                }
        }

        if (!first)
            putchar('\n');
        else
            first = false;

        printf("%d\n", topo(count));
    }

    return 0;
}
int topo(int count)
{
    queue<int> Q;

    //起點為第0個事件
    Q.push(0);
    Ref[0] = -1;

    int dp[N] = { 1 };

    while (!Q.empty())
    {
        int next = Q.front();
        Q.pop();

        for (int k : v[next])
        {
            //因為已沒有任何邊指向 next 了，到 k 的方法多加上 到 next 的方法數(next 可以到 k)
            dp[k] += dp[next];

            //更新 Ref
            if (Ref[k] != -1)
            {
                Ref[k]--;
                if (!Ref[k])
                {
                    Q.push(k);
                    Ref[k] = -1;
                }
            }
        }
    }
    
    //把到各死亡事件的走法相加即為答案
    int sum = 0;
    for (int i = 0; i < count; i++)
        sum += dp[death[i]];

    return sum;
}