首页 > 其他 > 详细

Graph

时间:2016-08-22 09:19:35      阅读:151      评论:0      收藏:0      [点我收藏+]

 

Graph
( graph .cpp/c/pas)
Description
小 Y 又开始了一段旅途。
这次,他要经过一个图,从 号点到达 号点,每个点设有休息站。
小 Y 计划用最多 天走完全程,除第 天外,每一天小 Y 都必须在休息站过夜。所以,一段路
必须在同一天走完。
小 Y 的体力有限,他希望走的路程最大的一天中走的路尽可能少,请求出这个最小值。
Input
第一行三个整数 、 、 表示图的顶点数、边数、天数。
从第二行开始,之后的 行,每行三个整数 、 、 表示从 和 间有一条双向道路,长度
为 。
Output
一行一个正整数,如果小 Y 能走完全程,输出走的路程最大的一天中走的路程最小值,否则输
出 。
Example
graph.in graph.out
3 2 4
3 2 4
1 2 1
4
附加样例见选手目录下『graph』文件夹。
Hint
对于 的数据, ;
对于 的数据, ;
对于 的数据, , , ;
保证没有重边和自环。

 

 

 

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node{
    int T,T1,T2;
}a[200001];
int m,n,k,ans=-1,F[7501];
int Find(int t)//找爹 
{
    if (F[t]==t)
      return t;
    return F[t]=Find(F[t]);
}
bool Check(int t)
{
    for (int i=1;i<=n;i++)
      F[i]=i;
    for (int i=1;i<=m;i++)
    {
          if (a[i].T>t)
            continue;
          int t1=Find(a[i].T1);
          int t2=Find(a[i].T2);
          if (t1!=t2)
            F[t2]=t1;
          if (Find(1)==Find(n))
            return true;
    }
    return false;
}
int main()
{
    //freopen("graph.in","r",stdin);
    //freopen("graph.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    int maxn=0;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].T1,&a[i].T2,&a[i].T);
        maxn=max(maxn,a[i].T);
    }
    int Left=0,Right=maxn;//二分删边 
    while (Left<=Right)
    {
        int Mid=(Left+Right)>>1;
        if (Check(Mid))
        {
            ans=Mid;
            Right=Mid-1;
        }
        else
          Left=Mid+1;
    }
    printf("%d",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

 

Graph

原文:http://www.cnblogs.com/xiaoningmeng/p/5794288.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!