题意：
邦德在逃命！他在一个有N个城市，由M条边连接的道路网中。一条路的危险度被定义为这条路上危险度最大的边的危险度。
现在给出若干个询问，s，t，问从s到t的最小的危险度是多少。
思路：
首先可以证明这条路是固定的，就是最小生成树，证明略。
之后就是计算生成树上两点间的最长边，用prim算法预处理的话，由于N的规模较大，所以会超时。
由于MST是一棵树，想到树上两点之间的距离有O(log(n))的求法，即倍增求lca，按照同样的处理方法，只不过维护最大值，就可以在O(log(n))的时间内求出两点之间的最长边，查询为Q，总复杂度Qlog(n)。
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 50005; 9 //const int inf = 0x3f3f3f3f; 10 11 struct edge 12 { 13 int fr,to,len; 14 15 edge(int a,int b,int c) 16 { 17 fr = a; 18 to = b; 19 len = c; 20 } 21 }; 22 23 bool cmp(edge x,edge y) 24 { 25 return x.len < y.len; 26 } 27 28 vector g[maxn],es; 29 int p[maxn][35]; 30 int fa[maxn]; 31 int par[maxn]; 32 bool vis[maxn]; 33 int md[maxn][35]; 34 int deep[maxn]; 35 36 int fin(int x) 37 { 38 if (x == par[x]) return x; 39 else return par[x] = fin(par[x]); 40 } 41 42 void unit(int x,int y) 43 { 44 x = fin(x); 45 y = fin(y); 46 47 if (x == y) return; 48 49 par[x] = y; 50 } 51 52 void dfs(int u) 53 { 54 vis[u] = 1; 55 56 for (int i = 0;i < g[u].size();i++) 57 { 58 edge e = g[u][i]; 59 60 int to = e.to; 61 62 if (vis[to]) continue; 63 64 fa[to] = u; 65 66 deep[to] = deep[u] + 1; 67 68 md[to][0] = e.len; 69 70 dfs(to); 71 } 72 } 73 74 void pre_deal(int n) 75 { 76 for (int i = 0;i <= n;i++) 77 { 78 p[i][0] = fa[i]; 79 } 80 81 //int sz = (int)(log(n*1.0) / log(2.0)) + 1; 82 83 for (int j = 1;j<= 20;j++) 84 { 85 for (int i = 1;i <= n;i++) 86 { 87 p[i][j] = p[p[i][j-1]][j-1]; 88 md[i][j] = max(md[i][j-1],md[p[i][j-1]][j-1]); 89 } 90 } 91 } 92 93 int query(int a,int b,int n) 94 { 95 if (deep[a] < deep[b]) swap(a,b); 96 97 int c = deep[a] - deep[b]; 98 99 int ans = 0;100 101 //int sz = (int)(log(n * 1.0) / log(2.0)) + 1;102 103 for (int i = 0;i <= 20;i++)104 {105 if (c & (1 << i))106 {107 ans = max(ans,md[a][i]);108 a = p[a][i];109 //printf("%d **\n",ans);110 } 111 }112 113 if (a == b) return ans;114 else115 {116 for (int i = 20;i >= 0;i--)117 {118 if (p[a][i] != p[b][i])119 {120 ans = max(ans,md[a][i]);121 ans = max(ans,md[b][i]);122 123 a = p[a][i];124 b = p[b][i];125 }126 }127 }128 129 ans = max(ans,md[a][0]);130 ans = max(ans,md[b][0]);131 132 return ans;133 }134 135 void init(int n)136 {137 for (int i = 0;i <= n;i++)138 {139 g[i].clear();140 par[i] = i;141 }142 143 es.clear();144 145 memset(vis,0,sizeof(vis));146 memset(md,0,sizeof(md));147 memset(deep,0,sizeof(deep));148 memset(md,0,sizeof(md));149 }150 151 int main()152 {153 int n,m;154 155 int kase = 0;156 157 while (scanf("%d%d",&n,&m) != EOF)158 {159 if (kase++) printf("\n");160 161 init(n);162 163 for (int i = 0;i < m;i++)164 {165 int a,b,c;166 167 scanf("%d%d%d",&a,&b,&c);168 169 es.push_back(edge(a,b,c));170 }171 172 sort(es.begin(),es.end(),cmp);173 174 for (int i = 0;i < m;i++)175 {176 int x = es[i].fr,y = es[i].to;177 178 if (fin(x) == fin(y)) continue;179 180 unit(x,y);181 182 g[x].push_back(edge(x,y,es[i].len));183 g[y].push_back(edge(y,x,es[i].len));184 }185 186 deep[1] = 0;187 //188 dfs(1);189 //printf("233\n");190 pre_deal(n);191 192 int q;193 194 scanf("%d",&q);195 196 for (int i = 0;i < q;i++)197 {198 int a,b;199 200 int ans = 0;201 202 scanf("%d%d",&a,&b);203 204 ans = query(a,b,n);205 206 printf("%d\n",ans);207 }208 }209 210 return 0;211 }