Problem Solving►UVa

UVa 10099 - The Tourist Guide

Contents

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

Problem

題目網址
中文網址

Solution

注意導遊也算在內，所以在建邊時乘載量要扣一。
由於是要求最少趟，所以希望路線上的最小乘載量越大越好(bottleneck)。

建最大生成樹，利用 Kruskal 每次都先取較大的邊，直到起點和終點都在樹上，此時的邊即是 bottleneck。
(由於從大取到小，不會有低估的情形)

Code

UVa 10099
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
#include <cstdio>
#include <algorithm>
#define N 101
#define R 10005

struct edge
{
    int u, v, w;
};
int p[N];

inline void init(int n)
{
    for (int i = 0; i <= n; i++)
        p[i] = i;
}
inline int find(int x)
{
    return (x == p[x]) ? x : (p[x] = find(p[x]));
}
inline void Union(int a, int b)
{
    p[find(a)] = find(b);
}
int main()
{
    edge e[R];
    int n, r, Case = 1;
    while (scanf("%d%d", &n, &r) && (n || r))
    {
        r <<= 1;
        for (int i = 0; i < r; i += 2)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            e[i].u = e[i + 1].v = u;
            e[i].v = e[i + 1].u = v;
            e[i].w = e[i + 1].w = w - 1; //include tourist guide
        }

        int beg, end, all, ans;
        scanf("%d%d%d", &beg, &end, &all);

        //由大排到小
        std::sort(e, e + r, [](const edge &a, const edge &b) -> bool { return a.w > b.w; });

        //kruskal
        init(n);
        for (int i = 0, j = 0; i < n - 1 && j < r; ++i)
        {
            while (find(e[j].u) == find(e[j].v))
                ++j;

            Union(e[j].u, e[j].v);

            //已經找到起點到終點的路徑
            if (find(beg) == find(end))
            {
                ans = e[j].w; //先前建的邊一定比現在大
                break;
            }
        }

        printf("Scenario #%d\n", Case++);
        printf("Minimum Number of Trips = %d\n\n", all / ans + ((all % ans) ? 1 : 0));
    }

    return 0;
}