UVa 10099:The Tourist Guide(Floyd, 最大生成树)

链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1040

题目:

Problem D

The Tourist Guide

Input: standard input

Output: standard output

Mr. G. works as a tourist guide. His current assignment is to take some tourists from one city to another. Some two-way roads connect the cities. For each pair of neighboring cities there is a bus service that runs only between those two cities and uses the road that directly connects them. Each bus service has a limit on the maximum number of passengers it can carry. Mr. G. has a map showing the cities and the roads connecting them. He also has the information regarding each bus service. He understands that it may not always be possible for him to take all the tourists to the destination city in a single trip. For example, consider the following road map of 7 cities. The edges connecting the cities represent the roads and the number written on each edge indicates the passenger limit of the bus service that runs on that road.

Now, if he wants to take 99 tourists from city 1 to city 7, he will require at least 5 trips, since he has to ride the bus with each group, and the route he should take is : 1 - 2 - 4 - 7.

But, Mr. G. finds it difficult to find the best route all by himself so that he may be able to take all the tourists to the destination city in minimum number of trips. So, he seeks your help.

Input

The input will contain one or more test cases. The first line of each test case will contain two integers: N (N<= 100) and R representing respectively the number of cities and the number of road segments. Then R lines will follow each containing three integers: C1, C2 andP. C1 and C2 are the city numbers and P (P> 1) is the limit on the maximum number of passengers to be carried by the bus service between the two cities. City numbers are positive integers ranging from 1 to N. The (R + 1)-th line will contain three integers: S, D andT representing respectively the starting city, the destination city and the number of tourists to be guided.

The input will end with two zeroes for N and R.

Output

For each test case in the input first output the scenario number. Then output the minimum number of trips required for this case on a separate line. Print a blank line after the output of each test case.

Sample Input

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0

Sample Output
Scenario #1
Minimum Number of Trips = 5

分析与总结:

和上一题UVa 10048 - Audiophobia(Floyd, Kruskal)基本类似,  a到b的所有路径,每条路径上都有一个最小的权值x, 求所有路径中的最大的x。

求出x之后,要算出一共要走几个来回,每个来回带一组人到目标,那么只需要直接 T/(x-1)【向上取整】,便得到答案, T为导游所带的总人数。

特别需要注意是每一趟带的人数是x-1, 因为导游也要占一个位置。

代码:

1.Kruskal方法

#include<cstdio>
#include<algorithm>
#define N 10005
using namespace std;  

int n,m,beg,end,limit,f[N],rank[N];  

struct Edge{
    int u,v,val;
    friend bool operator<(const Edge&a,const Edge&b){
        return a.val>b.val;
    }
}arr[N];  

inline void init(){
    for(int i=0; i<=n; ++i)
        f[i]=i,rank[i]=0;
}
int find(int x){
    int i,j=x;
    while(j!=f[j]) j=f[j];
    while(x!=j){
        i=f[x]; f[x]=j; x=i;
    }
    return j;
}
bool Union(int x,int y){
    int a=find(x),b=find(y);
    if(a==b)return false;
    if(rank[a]>rank[b])
        f[b]=a;
    else{
        if(rank[a]==rank[b])
            ++rank[b];
        f[a]=b;
    }
    return true;
}  

int main(){
    int a,b,c,cas=1;
    while(~scanf("%d%d",&n,&m)&&n+m){
        for(int i=0; i<m; ++i){
             scanf("%d%d%d",&a,&b,&c);
             arr[i].u=a,arr[i].v=b,arr[i].val=c;
        }
        scanf("%d%d%d",&beg,&end,&limit);
        init();
        sort(arr,arr+m);
        int ans;
        for(int i=0; i<m; ++i){
            Union(arr[i].u,arr[i].v);
            a=find(beg), b=find(end);
            if(a==b){
                ans = arr[i].val;
                break;
            }
        }
        int t=(limit%(ans-1)==0)?(limit/(ans-1)):(limit/(ans-1)+1);
        printf("Scenario #%d\n", cas++);
        printf("Minimum Number of Trips = %d\n\n",t);
    }
    return 0;
}

2. Floyd

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索service
, number
, each
, to
, The
, that
10048
tourist guide、tourist、tourist acm、thesinhtourist、tourist attraction,以便于您获取更多的相关知识。

时间: 2025-01-29 12:39:06

UVa 10099:The Tourist Guide(Floyd, 最大生成树)的相关文章

uva 10099 The Tourist Guide

点击打开链接uva 10099 题目意思: 有一个旅游团现在去出游玩,现在有n个城市,m条路.由于每一条路上面规定了最多能够通过的人数,现在想问这个旅游团人数已知的情况下最少需要运送几趟 思路:最大生成树 + kruskal 分析:从题目可以知道从起始点到达终点的路径可能会有很多条,但是现在要求运送的次数最少,那么就是要满足每一次的运送都能够达到最多的人数.那么这就转变成求在满足条件的所有路径中所有边最小值中的最大值.那么只要按照求解最小生成树的过程,把排序改成按照大的排序然后在生成树的时候判断

UVa 567:Risk (Floyd)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=508 题目: Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world m

最小生成树【完结】

第一题 hdu 1232 畅通工程 点击打开hdu 1232 思路:模板题 点击查看代码 第二题 hdu 1233 还是畅通工程 点击打开hdu 1233 思路:模板题 点击查看代码 第三题 uva 10034 Freckles 点击打开uva 10034 思路:模板题 点击查看代码 第四题 uva 10397 Connect the Campus 点击打开uva 10397 思路:模板题 点击查看代码 第五题 uva 10369 Arctic Network 点击打开uva 10369 思路:

华为面试题算什么,这个背会了外企随便进

我为各位整理出英文面试最常见的五大问题,并且提醒各位一些回答的技巧,希望大家能针对这些问题多演练,当成练习英文面试的重点.  问题一:Could you please describe yourself?(能否请你形容一下自己?) 这个问题,一来是想要了解你是什么样的人,二来是想看看你是否知道如何重点式地自我简介. 在回答时,要针对应征工作的性质来凸显自己的特色,可以多用形容词,并且引用过去的工作经验,但是不必提及公司组织的名称,再者,你还可以谈谈未来的生涯规画:但如果你是个社会新鲜人,就可以谈

UVa 10048:Audiophobia(Floyd, Kruskal)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=989 题目: Problem B: Audiophobia Consider yourself lucky! Consider yourself lucky to be still breathing and having fun participati

uva oj 567 - Risk(Floyd算法)

/* 一张有20个顶点的图上. 依次输入每个点与哪些点直接相连. 并且多次询问两点间,最短需要经过几条路才能从一点到达另一点. bfs 水过 */ #include<iostream> #include<cstring> #include<vector> #include<cstdio> #include<queue> using namespace std; struct node{ int x, step; node(){ } node(in

UVa 131 The Psychic Poker Player:枚举&amp;amp;模拟好题

131 - The Psychic Poker Player Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=67 In 5-card draw poker, a player is dealt a hand of five cards (which may

UVA之11549 - Calculator Conundrum

[题目] Problem C CALCULATOR CONUNDRUM Alice got a hold of an old calculator that can display n digits. She was bored enough to come up with the following time waster. She enters a number k then repeatedly squares it until the result overflows. When the

uva 567 Risk

点击打开链接uva 567 1思路:最短路+floyd 2分析:题目给定的点的个数为20,那么根据f'loyd的时间复杂度不会超时,那么直接利用floyd即可. 3注意输出的格式问题 代码: #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 25 #define INF 0xFFFFFFF in