[TIOJ] 1163. 6.施工中的道路
題目連結: http://tioj.infor.org/problems/1163 本題看似給定一張無向圖，實在不好求得所有路徑最大值的最小值，但是很明顯可以發現因為是要最小的最大值，所以其實先把最小生成樹找出來後，再在上面求路徑最大值就會是好的，而且如果是寫kruskal演算法，你還可以快速知道兩個點是不是連通的。而要求一棵樹上路徑的最大值，不難發現你可以把路徑拆成a到LCA(a,b)跟b到LCA(a,b) (其中LCA指的是最低共同祖先)，然後通常求LCA時會用倍增法，而這時就會發現其實求路徑最大值也可以用倍增法，一樣每次更新這段的最大值，然後找的時候也差不多。 p.s 比較好的講法可以看 這篇 #include <bits/stdc++.h>
using namespace std;
#define N 30000
#define logN 16
typedef pair<int,int> PII;
int djs[N+5];
int Query(int x){if(djs[x]!=x)djs[x]=Query(djs[x]);return djs[x];}
inline void Merge(int a,int b){djs[Query(a)]=Query(b);}
struct Edge{
int s,e,p;
bool operator>(const Edge& x)const{return p>x.p;}
};
vector<PII> Tree[N+5];
int time_in[N+5], time_out[N+5],timer=0;
PII ff[N+1][logN+1];
void dfs(int,int,int);
inline bool anc(int,int);
inline int lca(int,int);
inline int getMax(int,int);
bitset<N+5> walked;
int main(){
ios_base::s...