题目链接：http://www.luogu.org/problem/show?pid=1967
数据：http://www.cnblogs.com/wanglichao/p/5592058.html
题目描述
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入输出格式
输入格式：
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道
路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出格式：
输出文件名为 truck.out。
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货
车不能到达目的地，输出-1。
输入输出样例
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
3 -1 3
说明
对于 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。
这题实在坑啊，一开始TLE+MLE+RE
后来发现自己空间算错，均摊一下发现其实空间是O(n)的（本来差点开了n2），解决了RE和MLE
然后改半天然后发觉自己没打路径压缩（woc，实在太久没打并查集了）
然后就A了233
题解：
第一步转化：
原图中的一部分边是可以删的，只要保留其中的最大生成树即可
写个并查集，用贪心，每次把权最大的边加入，合并两个集合，同时生成树
网上有个好方法（忘记是哪位大牛的了）对于每一条边，都新建一个点，作为“它连接的两个点的根节点”的根节点，因为是最大生成树，每次添加边时，两个点肯定不是同一棵树（同一个并查集）里的，所以这样保证可以生成一棵树（最开心的是这还是二叉树233）
还有一个隐藏小问题：你做出来的是个森林，不是一棵树，MDZZ怎么办？
我用的是相当低效的办法：在二叉树上加一大堆点（在原图里这些点都是权为0的边），显然不会影响结果，但现在想想不保留二叉树性质也无妨，而且只要加一个根节点就可以了……（主要是我是写了一半才发现这个问题——天然迟钝——二叉树都打完了，懒得改），这样一来边数应该就是n-1了（都连通了）。
既然是一棵树上了，那么就只要找出一条路径，做一遍LCA即可
1.Tarjan离线
据说可以Tarjan离线，但是我并不打算这么写，毕竟现在写在线的总是比离线的心里有底一点（离线几乎没写过，上次莫队的题目被我直接跳过了）
2.RMQ在线
我的方法：
再做一遍转化，根据dfs顺序把树摊开来：
比如样例中的数据
（懒得网上找了，自己画一个）
大图地址：http://www.cnblogs.com/wanglichao/gallery/image/170185.html
就是每次dfs找到一个点（包括回溯回来以后又一次经过）就记录一次（同时记录深度）
如果知道两个点在序列中的位置（第一次出现），就可以得到他们根节点的编号（即两点间深度最小的点）
于是就变成了神奇的区间最小值问题
先预处理做一遍dp，预处理出每一小块的最小值
使dp[i][j]为从i开始的2j个元素的最小值
很容易想到从j-1到j的转移方程（比一比就行了）
dp[i][j]=min(dp[i][j-1],dp[i+2j-1][j-1])
在每一次询问中只要找到小于等于区间大小的最大的2的幂，比一下两个dp就可以了
（连画图都懒得用）
dp[x][j]
----------------------------------
| | y是结尾
*******************************************这是要找最小值的数据
x是开头 | |
------------------------------
dp[y-2j+1][j]
min(dp[y-2j+1][j],dp[x][j])即为询问的答案
然后把路径上各个非叶子节点（也就是原图上的边）的最小值求一下
若为0则不连通，非0则输出
问题解决
上代码
#include <cstdio> #include <algorithm> using namespace std; struct haha { int a,b,c; } a[50001]; bool com(haha a,haha b) { return (a.c>b.c); } int d[200001],e[200001],po[10001],l[70001],r[70001],f[70001],gp[70001],dp[150001][30],_dp[150001][30],p[150001],q[150001]; int n,m,_n; int read(){ int x=0; char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x; } int dfs(int k,int p,int q)//把图按dfs顺序转成表 { d[p]=q; e[p]=k; int ans=0; if(k<=n) { po[k]=p; return 1; } ans+=dfs(l[k],p+1,q+1); ans++; d[p+ans]=q; e[p+ans]=k; ans+=dfs(r[k],p+ans+1,q+1); ans++; d[p+ans]=q; e[p+ans]=k; return ++ans; } int fa(int p)//求并查集的祖先（其实是树的根节点） { if(f[gp[p]]==gp[p]) return gp[p]; else { gp[p]=fa(f[gp[p]]); return gp[p]; } } void init()//处理输入的图，添加0边，生成一棵最大生成树（避免森林） { sort(a+1,a+m+1,com); for(int i=1;i<=n+m;i++) { f[i]=i; gp[i]=i; } for(int i=1;i<=m;i++) if(fa(a[i].a)!=fa(a[i].b)) { f[n+i]=n+i; l[n+i]=fa(a[i].a); r[n+i]=fa(a[i].b); f[fa(a[i].a)]=n+i; f[fa(a[i].b)]=n+i; } int _i=n+m; for(int i=1;i<n;i++) if(fa(i)!=fa(i+1)) { _i++; f[_i]=_i; gp[_i]=_i; l[_i]=fa(i); r[_i]=fa(i+1); f[fa(i)]=_i; f[fa(i+1)]=_i; } } void calc()//求区间最小值预处理 { for(int i=1;i<=_n;i++) { dp[i][0]=d[i]; _dp[i][0]=i; } int j=1,k=2; while(k<=_n) { for(int i=1;i<=_n-k+1;i++) if(dp[i][j-1]<dp[i+k/2][j-1]) { dp[i][j]=dp[i][j-1]; _dp[i][j]=_dp[i][j-1]; } else { dp[i][j]=dp[i+k/2][j-1]; _dp[i][j]=_dp[i+k/2][j-1]; } j++; k*=2; } k=1;j=0; for(int i=1;i<=_n;i++) { if(i>=2*k) { k*=2; j++; } p[i]=j; q[i]=k; } } int lca(int x,int y)//求区间最小值 { return (dp[x][p[y-x+1]]>dp[y-q[y-x+1]+1][p[y-x+1]])?_dp[y-q[y-x+1]+1][p[y-x+1]]:_dp[x][p[y-x+1]]; } int main() { n=read(); m=read(); for(int i=1;i<=m;i++) { a[i].a=read(); a[i].b=read(); a[i].c=read(); } init(); _n=dfs(fa(1),1,0); calc(); m=read(); for(int i=1;i<=m;i++) { int x,y; x=read(); y=read(); x=po[x];y=po[y]; if(x>y) swap(x,y); int o=lca(x,y),sum=a[e[o]-n].c; for(x=f[e[x]];x!=e[o];x=f[x]) sum=min(sum,a[x-n].c); for(y=f[e[y]];y!=e[o];y=f[y]) sum=min(sum,a[y-n].c); printf("%d ",sum?sum:-1); } return 0; }