Bond UVA

Once again, James Bond is on his way to saving the world. Bond's latest mission requires him to travel between several pairs of cities in a certain country.

The country has N cities (numbered by 1, 2, . . ., N), connected by M bidirectional roads. Bond is going to steal a vehicle, and drive along the roads from city s to city t. The country's police will be patrolling the roads, looking for Bond, however, not all roads get the same degree of attention from the police.

More formally, for each road MI6 has estimated its dangerousness, the higher it is, the more likely Bond is going to be caught while driving on this road. Dangerousness of a path from s to t is defined as the maximum dangerousness of any road on this path.

Now, it's your job to help Bond succeed in saving the world by finding the least dangerous paths for his mission.

Input

There will be at most 5 cases in the input file.

The first line of each case contains two integers N, M (2 ≤ N≤ 50000, 1≤ M ≤ 100000) – number of cities and roads. The next M lines describe the roads. The i-th of these lines contains three integers: x_i, y_i, d_i (1 ≤ x_i, y_i ≤ N, 0 ≤ d_i ≤ 10⁹) - the numbers of the cities connected by the ith road and its dangerousness.

Description of the roads is followed by a line containing an integer Q (1 ≤ Q ≤ 50000), followed by Q lines, the i-th of which contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ N, s_i !=t_i).

Consecutive input sets are separated by a blank line.

Output

For each case, output Q lines, the i-th of which contains the minimum dangerousness of a path between cities s_i and t_i. Consecutive output blocks are separated by a blank line.

The input file will be such that there will always be at least one valid path.

LCA实际应用的一个题目

题意：

N个城市 M条路保证可以联通，有q个询问，求出从x走到y的最短路径上的最大边长

如果对于LCA还有什么不理解的话，可以看我的上一篇随笔，LCA倍增算法详解。

如果还有不懂可以留言给我

根据题意应该先生成一个最小生成树，然后通过LCA求出最短路径上的最大边长；

此题对于格式卡的非常死。注意格式

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 #include<iostream>
  8 #include <iomanip>
  9 using namespace std;
 10 const int maxn=50010;
 11 const int INF=100000000;
 12 struct node1 {
 13     int u,v,f;
 14 }qu[maxn*2];
 15 struct node2 {
 16     int x,y;
 17     node2 (int x=0 ,int y=0):x(x),y(y){};
 18 };
 19 vector<node2>a[maxn];
 20 int n,m,pre[maxn],fa[maxn],rk[maxn],cost[maxn];
 21 int anc[maxn][30],maxcost[maxn][30];
 22 int cmp1(node1 a,node1 b){
 23     return a.f<b.f;
 24 }
 25 int find(int x){
 26     while(x!=pre[x]) x=pre[x];
 27     return x;
 28 }
 29 void dfs(int u,int f,int depth){
 30     rk[u]=depth;
 31     fa[u]=u;
 32     int len=a[u].size();
 33     for (int i=0 ;i<len ;i++){
 34         int v=a[u][i].x;
 35         int w=a[u][i].y;
 36         if (v!=f) {
 37             dfs(v,u,depth+1);
 38             fa[v]=u;
 39             cost[v]=w;
 40         }
 41     }
 42 }
 43 void lca(){
 44     for (int i=1 ;i<=n ;i++){
 45         anc[i][0]=fa[i];
 46         maxcost[i][0]=cost[i];
 47         for (int j=1 ;(1<<j)<=n ;j++){
 48             anc[i][j]=-1;
 49         }
 50     }
 51     for (int j=1 ;(1<<j)<=n ;j++){
 52         for (int i=1 ;i<=n ;i++){
 53             if (anc[i][j-1]!=-1) {
 54                 anc[i][j]=anc[anc[i][j-1]][j-1];
 55                 maxcost[i][j]=max(maxcost[i][j-1],maxcost[anc[i][j-1]][j-1]);
 56             }
 57         }
 58     }
 59 }
 60 int query(int x,int y){
 61     if (rk[x]<rk[y]) swap(x,y);
 62     int k,ans=-INF;
 63     for (k=1 ;(1<<(1+k))<=rk[x] ;k++) ;
 64     for (int i=k ;i>=0 ;i--){
 65         if (rk[x]-(1<<i)>=rk[y]) {
 66             ans=max(ans,maxcost[x][i]);
 67             x=anc[x][i];
 68         }
 69     }
 70     if (x==y) return ans;
 71     for (int i=k ;i>=0 ;i--){
 72         if (anc[x][i]!=-1 && anc[x][i]!=anc[y][i] ){
 73             ans=max(ans,maxcost[x][i]);
 74             x=anc[x][i];
 75             ans=max(ans,maxcost[y][i]);
 76             y=anc[y][i];
 77         }
 78     }
 79     ans=max(ans,max(cost[x],cost[y]));
 80     return ans;
 81 }
 82 int  main() {
 83     int flag=1 ;
 84     while(scanf("%d%d",&n,&m)!=EOF){
 85         if (flag==0) printf("
");
 86         flag=0;
 87         for (int i=0 ;i<m ;i++)
 88             scanf("%d%d%d",&qu[i].u,&qu[i].v,&qu[i].f);
 89         sort(qu,qu+m,cmp1);
 90         for (int i=0 ;i<=n ;i++ ){
 91             a[i].clear();
 92             pre[i]=i;
 93         }
 94         for (int i=0 ;i<m ;i++){
 95             int x=find(qu[i].u);
 96             int y=find(qu[i].v);
 97             if (x!=y) {
 98                 pre[x]=y;
 99                 a[x].push_back(node2(y,qu[i].f));
100                 a[y].push_back(node2(x,qu[i].f));
101             }
102         }
103         dfs(1,-1,0);
104         lca();
105         int q;
106         scanf("%d",&q);
107         while(q--){
108             int x,y;
109             scanf("%d%d",&x,&y);
110             printf("%d
",query(x,y));
111         }
112     }
113     return 0;
114 }

相关推荐