题目来源：UVa 11354 Bond

题意：n个点m条边的图 q次询问 找到一条从s到t的一条边 使所有边的最大危险系数最小

思路：使最大的危险系数尽量小 答案是最小生成树上的边 然后用LCA倍增法记录s和t到他们最近公共祖先的最大值

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 50010; const int INF = 0x3f3f3f3f; int anc[maxn][30], maxcost[maxn][30]; int fa[maxn], L[maxn], cost[maxn], vis[maxn], f[maxn]; int n, m; int first[maxn], cnt; struct edge { int u, v, w, next; }e[maxn*2], e2[maxn*8]; bool cmp(edge a, edge b) { return a.w < b.w; } void AddEdge(int u, int v, int w) { e2[cnt].v = v; e2[cnt].w = w; e2[cnt].next = first[u]; first[u] = cnt++; e2[cnt].v = u; e2[cnt].w = w; e2[cnt].next = first[v]; first[v] = cnt++; } void pre() { for(int i = 1; i <= n; i++) { anc[i][0] = fa[i]; maxcost[i][0] = cost[i]; for(int j = 1; (1<
     
      = 0; i--) if(L[p] - (1<
      
       = L[q]) { ans = max(ans, maxcost[p][i]); p = anc[p][i]; } if(p == q) return ans; for(int i = log; i >= 0; i--) { if(anc[p][i] != -1 && anc[p][i] != anc[q][i]) { ans = max(ans, maxcost[p][i]); ans = max(ans, maxcost[q][i]); p = anc[p][i]; q = anc[q][i]; } } ans = max(ans, cost[p]); ans = max(ans, cost[q]); return ans; } void dfs(int u) { for(int i = first[u]; i != -1; i = e2[i].next) { int v = e2[i].v; if(vis[v]) continue; vis[v] = 1; fa[v] = u; cost[v] = e2[i].w; L[v] = L[u]+1; dfs(v); } } int find(int x) { if(f[x] != x) return f[x] = find(f[x]); return x; } int main() { int cas = 0; while(scanf("%d %d", &n, &m) != EOF) { memset(first, -1, sizeof(first)); memset(vis, 0, sizeof(vis)); cnt = 0; for(int i = 0; i < m; i++) { scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); } sort(e, e+m, cmp); for(int i = 0; i <= n; i++) f[i] = i; int sum = 0; for(int i = 0; i < m; i++) { int u = e[i].u; int v = e[i].v; int x = find(u); int y = find(v); if(x != y) { sum++; f[x] = y; AddEdge(e[i].u, e[i].v, e[i].w); } } fa[1] = -1; cost[1] = 0; L[1] = 0; vis[1] = 1; dfs(1); pre(); int q; scanf("%d", &q); if(cas++) printf("\n"); while(q--) { int u, v; scanf("%d %d", &u, &v); printf("%d\n", query(u, v)); } } return 0; }