Wikioi 3287 货车运输
题目描述 Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出描述 Output Description
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
样例输入 Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出 Sample Output
3
-1
3
数据范围及提示 Data Size & Hint
对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000；
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。
思路：
lca模板题
代码：
1 include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #include<vector> 7 #define mx 50050 8 #define maxint 100000000 9 #define mp 30 10 using namespace std; 11 struct Edge{ 12 int v; 13 int w; 14 }; 15 struct Edget{ 16 int u; 17 int v; 18 int w; 19 }; 20 int n,m,q,pre[mx],pos = 0,f[mx][mp],deep[mx]; 21 vector<Edge> edge[mx]; 22 Edget edget[mx]; 23 bool cmp(Edget a,Edget b){ 24 return a.w > b.w; 25 } 26 int find(int x) 27 { 28 int r=x; 29 while ( pre[r ] != r ) 30 r=pre[r ]; 31 32 int i=x , j ; 33 while( i != r ) 34 { 35 j = pre[ i ]; 36 pre[ i ]= r ; 37 i=j; 38 } 39 return r ; 40 } 41 42 43 void join(int x,int y) 44 45 { 46 int fx=find(x),fy=find(y); 47 if(fx!=fy) 48 pre[fx ]=fy; 49 } 50 void dfs(int x) 51 { 52 int y,j,k; 53 vector<Edge>::iterator it; 54 y=f[x][0]; 55 deep[x]=deep[y]+1; 56 for (k=0;f[y][k]!=0;k++) { f[x][k+1]=f[y][k]; y=f[y][k]; } 57 for (it=edge[x].begin();it!=edge[x].end();it++) if ((it->v) != f[x][0]) 58 { 59 f[it->v][0]=x; dfs(it->v); 60 } 61 } 62 int findlca(int x,int y) 63 { 64 int z,k,dd; 65 if (deep[x]<deep[y]) {z=x; x=y; y=z;} 66 k=0; 67 for (dd=deep[x]-deep[y];dd!=0;dd=dd>>1) 68 { if (dd&1) x=f[x][k]; k++; } 69 if (x==y) return x; 70 k=0; 71 while (k>=0) 72 if (f[x][k]!=f[y][k]) {x=f[x][k];y=f[y][k]; k++;} 73 else k--; 74 return f[x][0]; 75 } 76 77 void output(){ 78 cout<<"pos : "<<pos<<endl; 79 for(int i = 0;i < pos;i++){ 80 cout<<edget[i].u<<" "<<edget[i].v<<" "<<edget[i].w<<endl; 81 } 82 vector<Edge>::iterator it; 83 for(int i = 1;i <= n;i++){ 84 cout<<i<<" :"<<endl; 85 for(it = edge[i].begin();it != edge[i].end();it++){ 86 cout<<"("<<it->v<<" , "<<it->w<<")"<<endl; 87 } 88 } 89 } 90 void input(){ 91 cin>>n>>m; 92 int x,y,z; 93 for(int i = 1;i <= m;i++){ 94 cin>>x>>y>>z; 95 edget[pos].w = z; 96 edget[pos].v = y; 97 edget[pos].u = x; 98 pos++; 99 100 } 101 } 102 void instruct(){ 103 sort(edget,edget+pos,cmp); 104 Edge tmp; 105 for(int i = 1;i <= n;i++) pre[i] = i; 106 for(int i = 0;i < pos;i++){ 107 if(find(edget[i].u) != find(edget[i].v)){ 108 join(edget[i].u,edget[i].v); 109 tmp.v = edget[i].v; 110 tmp.w = edget[i].w; 111 edge[edget[i].u].push_back(tmp); 112 tmp.v = edget[i].u; 113 edge[edget[i].v].push_back(tmp); 114 } 115 } 116 for(int i = 1;i <= n;i++) dfs(i); 117 118 } 119 void lca(){ 120 cin>>q; 121 int x,y,r,ans; 122 vector<Edge>::iterator it; 123 for(int i = 1;i <= q;i++){ 124 ans = maxint; 125 cin>>x>>y; 126 if(find(x) != find(y)){ 127 cout<<-1<<endl; 128 continue; 129 } 130 r = findlca(x,y); 131 for(int i = x;i != r;i = f[i][0]){ 132 for(it=edge[i].begin();it!=edge[i].end();it++){ 133 if(it->v == f[i][0]) ans = min(it->w,ans); 134 } 135 } 136 for(int i = y;i != r;i = f[i][0]){ 137 for(it=edge[i].begin();it!=edge[i].end();it++){ 138 if(it->v == f[i][0]) ans = min(it->w,ans); 139 } 140 } 141 cout<<ans<<endl; 142 } 143 144 } 145 int main(){ 146 input(); 147 instruct(); 148 lca(); 149 return 0; 150 }