By yusijia

Updated:

Contents
  1. 1. 题目意思：

题目意思：

有一个旅游团现在去出游玩，现在有n个城市，m条路。由于每一条路上面规定了最多能够
通过的人数，现在想问这个旅游团人数已知的情况下最少需要运送几趟（从a到b地，有
goal个人） 

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

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 110
#define INF 0x3f3f3f3f
using namespace std;
int n, m, father[MAXN], ranks[MAXN], Case;
int start, endss, goal;

struct Edge{
    int from;
    int to;
    int cost;
}edge[MAXN];

bool cmp(Edge e1, Edge e2){//将边按从大到小的顺序排序
    return e1.cost > e2.cost;
}

void init_set()
{
    for(int i = 1; i <= n; i++){
        father[i] = i;
        ranks[i] = 1;
    }
}

int find_set(int x)
{
    return x == father[x] ? father[x] : father[x] = find_set(father[x]);
}

void union_set(int x, int y)
{
    if(ranks[x] >= ranks[y]){
        ranks[x] += ranks[y];
        father[y] = x;
    }
    else{
        ranks[y] += ranks[x];
        father[x] = y;
    }
}

void kruskal()
{
    int ans = 0;
    init_set();
    sort(edge, edge + m, cmp);
    for(int i = 0; i < m; i++){
        int root_x = find_set(edge[i].from);
        int root_y = find_set(edge[i].to);
        if(root_x != root_y){  //如果没有连通
            union_set(root_x, root_y);
            if(find_set(start) == find_set(endss)){
                ans = edge[i].cost;  //边是从大到小排列的，如果循环到这条边,union后起点和终点通了
                break;            //就认为这条边的cost是整条通路能一趟运的最多人数，因为就算
                                  //前面的路可以一趟运30人，但这条路只能运20人，则认为整条路
                                  //最多也就一趟运20人
            }
        }
    }
    int add = 0;
    if(goal % (ans - 1))//看能否整数趟运完人，减一是因为有导游
        add = 1;        //如果不能，则要多运一趟
    printf("Scenario #%d\n" , Case++);
    printf("Minimum Number of Trips = %d\n\n" , goal / (ans - 1) + add);
}

int main()
{
    freopen("input.txt", "r", stdin);
    Case = 1;
    while(scanf("%d%d", &n, &m) != EOF && n+m){
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
        }
        scanf("%d%d%d", &start, &endss, &goal);
        kruskal();
    }
    return 0;
}
Contents
  1. 1. 题目意思：