[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::sync_with_stdio(0);cin.tie(0);
	int v,e;cin>>v>>e;
	for(int i=1;i<=v;i++)djs[i]=i;
	for(int i=1;i<=v;i++)for(int j=0;j<=logN;j++) ff[i+1][j]={i+1,0};
	priority_queue<Edge,vector<Edge>,greater<Edge>> pq;
	for(int i=0;i<e;i++){
		int s,e,p;cin>>s>>e>>p;
		pq.push({s,e,p});
	}
	while(!pq.empty()){
		auto tp=pq.top();pq.pop();
		if(Query(tp.s)!=Query(tp.e)){
			Merge(tp.s,tp.e);
			Tree[tp.s].push_back({tp.e, tp.p});
			Tree[tp.e].push_back({tp.s, tp.p});
		}
	}
	for(int i=1;i<=v;i++){
		if(walked[i])continue;
		timer=0;
		dfs(i,i,0);
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=logN;j++)
			ff[i][j] = {\
				ff[ ff[i][j-1].first ][j-1].first,\
			 	max(ff[ff[i][j-1].first][j-1].second, ff[i][j-1].second)\
			};
	int q;cin>>q;
	while(q--){
		int s,e;cin>>s>>e;
		if(s==e){
			cout<<"0\n";
		}else if(Query(s)==Query(e)){
			int lcase=lca(s,e);
			cout<<(max(getMax(s,lcase), getMax(e,lcase)))<<'\n';
		}else cout<<"-1\n";
	}
	return 0;
}

void dfs(int w,int f,int v){
	walked[w]=1;
	time_in[w]=++timer;
	ff[w][0]={f,v};
	for(auto i:Tree[w])
		if(i.first!=f)dfs(i.first,w,i.second);
	time_out[w]=++timer;
}
inline bool anc(int a,int b){
	return time_in[a]<=time_in[b] && time_out[b]<=time_out[a];
}
inline int lca(int a,int b){
	if(anc(b,a))return b;
	for(int j=logN;j>=0;j--)
		if(!anc(ff[b][j].first, a))b=ff[b][j].first;
	return ff[b][0].first;
}

inline int getMax(int a,int b){
	if(a==b)return 0;
	if(anc(b,a))swap(a,b);
	int mx=0;
	for(int j=logN;j>=0;j--){
		if(!anc(ff[b][j].first, a)){
			mx=max(ff[b][j].second, mx);
			b=ff[b][j].first;
		}
	}
	return max(mx,ff[b][0].second);
}