最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • POJ 3615 Cow Hurdles (Floyd算法)

    Cow Hurdles
    Time Limit: 1000MS   Memory Limit: 65536K
    Total Submissions: 6142   Accepted: 2752

    Description

    Farmer John wants the cows to prepare for the county jumping competition, so Bessie and the gang are practicing jumping over hurdles. They are getting tired, though, so they want to be able to use as little energy as possible to jump over the hurdles.

    Obviously, it is not very difficult for a cow to jump over several very short hurdles, but one tall hurdle can be very stressful. Thus, the cows are only concerned about the height of the tallest hurdle they have to jump over.

    The cows’ practice room has N (1 ≤ N ≤ 300) stations, conveniently labeled 1..N. A set of M (1 ≤ M ≤ 25,000) one-way paths connects pairs of stations; the paths are also conveniently labeled 1..M. Path itravels
    from station Si to station Ei and contains exactly one hurdle of height Hi (1 ≤ Hi ≤ 1,000,000). Cows must jump hurdles in any path they traverse.

    The cows have T (1 ≤ T ≤ 40,000) tasks to complete. Task i comprises two distinct numbers, Ai and Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N), which
    connote that a cow has to travel from station Ai to station Bi (by traversing over one or more paths over some route). The cows want to take a path the minimizes the height of the tallest hurdle they jump over when traveling
    from Ai to Bi . Your job is to write a program that determines the path whose tallest hurdle is smallest and report that height.
     

    Input

    * Line 1: Three space-separated integers: NM, and T
    * Lines 2..M+1: Line i+1 contains three space-separated integers: Si , Ei , and Hi 
    * Lines M+2..M+T+1: Line i+M+1 contains two space-separated integers that describe task i: Ai and Bi

    Output

    * Lines 1..T: Line i contains the result for task i and tells the smallest possible maximum height necessary to travel between the stations. Output ⑴ if it is impossible to travel between the two stations.

    Sample Input

    5 6 3
    1 2 12
    3 2 8
    1 3 5
    2 5 3
    3 4 4
    2 4 8
    3 4
    1 2
    5 1

    Sample Output

    4
    8

    Source

    USACO 2007 November Silver

    题意:有1头牛,要进行跳木桩训练,已知有n个木桩,而且知道m对木桩之间的高度差。但是它很懒,它想尽量的跳最小的高度就完成从任意1个木桩到任意1个木桩的跳跃,给m对点,问是不是存在最小的跳跃高度使得其能够完成跳跃,如果有就输出最小高度;否则输出⑴。

    解析:现在要记录路径“长度”,实际上是最大跳跃高度,说白了就是,这条路径上所经过的相邻两木桩之间的差值的最大值,由于只要能跳过这个高度差最大的,高度差小确当然能跳过去了。由因而求任意两木桩之间的最大高度差值的最小值,所以我们可以用Floyd算法,对其进行处理,处理以后得到的终究结果就是最大高度的最小值了。

    AC代码:

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define INF 123456789
    int a[302][302]; //最大高度的最小值矩阵

    int main(){
    int n, m, t;
    int x, y, w;
    while(scanf("%d%d%d", &n, &m, &t)!=EOF){
    for(int i=1; i<=n; i++) //初始化
    for(int j=1; j<=n; j++) a[i][j] = i==j ? 0 : INF;
    for(int i=1; i<=m; i++){ //读入高度差
    scanf("%d%d%d", &x, &y, &w);
    a[x][y] = min(a[x][y], w); //更新最大高度差
    }
    for(int k=1; k<=n; k++) //Floyd
    for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++){
    a[i][j] = min(a[i][j], max(a[i][k], a[k][j]));
    }
    for(int i=1; i<=t; i++){
    scanf("%d%d", &x, &y);
    printf("%d
    ", a[x][y]==INF ? ⑴ : a[x][y]); //输出,如果还是INF,那就代表不可达,二者时之间没有路径满足要求
    }
    }
    return 0;
    }

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » POJ 3615 Cow Hurdles (Floyd算法)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级