你活得不快乐的原因是：既无法忍受目前的状态，又没能力改变这一切，可以像只猪一样懒，却无法像只猪一样懒得心安理得。
（为什么我搜到的励志句子这么好笑哈哈哈）
Graph
题目描述
小 Y 又开始了一段旅途。
这次，他要经过一个图，从1号点到达n号点，每个点设有休息站。
小 Y 计划用最多k天走完全程，除第k天外，每一天小 Y 都必须在休息站过夜。所以，一段路必须在同一天走完。
小 Y 的体力有限，他希望走的路程最大的一天中走的路尽可能少，请求出这个最小值。
输入
第一行三个整数n、m、k表示图的顶点数、边数、天数。
从第二行开始，之后的 m 行，每行三个整数 ui、vi、wi表示从 ui和 vi间有一条双向道路，长度为wi。
输出
一行一个正整数，如果小 Y 能走完全程，输出走的路程最大的一天中走的路程最小值，否则输出−1。
样例输入 Copy
3 2 4
3 2 4
1 2 1
样例输出 Copy
4
提示
对于100%的数据，2≤n≤k≤7500，0≤m≤200000，1≤wi≤109；保证没有重边和自环。
等我复习完最小生成树就来写
题意： （好迷啊）
思路：
（1）最小生成树+思维：
我们求一下该图的最小生成树，如果起点和终点联通的话，答案就是最小生成树中的最大边权，否则就输出-1。为什么呢。
我们可以先这样想，我把最小生成树中的最大边权改为非最小生成树里的任意边权，都比该边权大。对于最小生成树来说，该边权是最大值，对于剩下的边权来说，该边权是最小值。这不就是题意吗！这个思维转化真的 妙（也可能是我太弱）
（2）并查集+二分
基于（1）的分析，我们可以借鉴01分数规划的思想进行二分，我从0~maxx（边权最大值）进行二分，在check时不使用比该点值大的边，看是否能连通起点和终点
代码：
最小生成树
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll #define inf 0x3f3f3f3f inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=1e6+7; struct node{ int a,b,w; bool operator<(const node &W)const{ return w<W.w; } }e[maxn]; int root[maxn]; int Find(int x){ if(root[x]!=x) root[x]=Find(root[x]); return root[x]; } int n,m,k; int u,v,w; bool flag; void Kruskal(){ sort(e+1,e+1+m); int tot=0; for(int i=1;i<=n;i++) root[i]=i;//初始化并查集 int res=-1,cnt=0; for(int i=1;i<=m;i++){ int a=e[i].a,b=e[i].b,w=e[i].w; a=Find(a),b=Find(b); if(a!=b){ root[a]=b; // res=max(res,w); cnt++; } if(Find(1)==Find(n)){ cout<<w<<endl; flag=1; break; } if(cnt==n-1) break; } } void AC(){ n=read();m=read();k=read(); for(int i=1;i<=m;i++){ e[i].a=read();e[i].b=read();e[i].w=read(); } Kruskal(); if(!flag) puts("-1"); } int main(){ AC(); return 0; }
并查集+二分
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll #define inf 0x3f3f3f3f inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=1e6+7; struct node{ int a,b,w; bool operator<(const node &W)const{ return w<W.w; } }e[maxn]; int root[maxn]; int n,m,k; int u,v,w; int maxx=-1; int Find(int x){ if(root[x]!=x) root[x]=Find(root[x]); return root[x]; } void init(){ for(int i=1;i<=n;i++) root[i]=i; } int check(int x){ init(); for(int i=1;i<=m;i++){ if(e[i].w>x) continue; int a=Find(e[i].a),b=Find(e[i].b); if(a!=b) root[b]=a; if(Find(1)==Find(n)) return 1; } return 0; } void AC(){ n=read();m=read();k=read(); for(int i=1;i<=m;i++){ e[i].a=read();e[i].b=read();e[i].w=read(); maxx=max(maxx,e[i].w); } //for(int i=1;i<=n;i++) root[i]=i; int l=0,r=maxx,res=-1; while(l<=r){ int mid=l+r >> 1; if(check(mid)) r=mid-1,res=mid; else l=mid+1; } out(res); } int main(){ AC(); return 0; }
如有不足，欢迎指正~
参考资料：
![[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集](https://ucc.alicdn.com/pic/developer-ecology/5554eff79239411c8300cad4838b1fe7.png?x-oss-process=image/resize,h_160,m_lfit)
![[Atcoder ABC222] F - Expensive Expense | 妙用树的直径 | Dijkstra](https://ucc.alicdn.com/pic/developer-ecology/de3deaf60a8c47e19f061114e6c4be7a.png?x-oss-process=image/resize,h_160,m_lfit)
