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; }
原文：http://www.cnblogs.com/xiaoningmeng/p/5794288.html