A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

输出格式

样例输入1

??4 3 1 2 4 2 3 3 3 1 1 31 3 1 4 1 3

样例输出1

3-13

每个测试点1s。

对于 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。

NOIP 2013 提高组 Day 1

首先,根据最大生成树的性质,能保证在最大生成树上运输货物比在其他边上运输更优

那么问题就转化到了在最大生成树上求连同两点的边的边权的最小值

那么怎么解决呢？ LCA！！

本题解决方法就是：最大生成树上求LCA

#include<cstdio>
#include<vector>
#include<algorithm>
#define MAXM 50010
#define MAXN 10010
using namespace std;
int N,M,z[MAXN],deep[MAXN],Q;
bool vis[MAXN];
struct Edge{int from,to,dist;}edge0[MAXM];
struct Tree{int to,dist;}father[MAXN];
vector<Tree> tree[MAXN];
bool cmp(Edge A,Edge B){return A.dist>B.dist;}
int findp(int x){return z[x]==x?x:z[x]=findp(z[x]);}
void addTree(int ff,int tt,int dd){tree[ff].push_back((Tree){tt,dd});}
void dfs(int u)
{
for(int i=0;i<tree[u].size();i++)
{
Tree &e=tree[u][i];
if(!vis[e.to])
{
vis[e.to]=1;
father[e.to].to=u;
father[e.to].dist=e.dist;
deep[e.to]=deep[u]+1;
dfs(e.to);
}
}
}
int lca(int a,int b)
{
int ret=2100000000;
if(deep[a] > deep[b])swap(a,b);
while(deep[a] != deep[b])ret=min(ret,father[b].dist),b=father[b].to;
while(a!=b)ret=min(ret,father[b].dist),b=father[b].to,ret=min(ret,father[a].dist),a=father[a].to;
return ret;
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)z[i]=i;
for(int i=1;i<=M;i++)
scanf("%d%d%d",&edge0[i].from,&edge0[i].to,&edge0[i].dist);
sort(edge0+1,edge0+1+M,cmp);
for(int i=1;i<=M;i++)
{
int aa=edge0[i].from,bb=edge0[i].to,cc=edge0[i].dist;
int f1=findp(aa),f2=findp(bb);
if(f1 == f2)continue;
z[f2]=f1;
addTree(aa,bb,cc);
addTree(bb,aa,cc);
}
for(int i=1;i<=N;i++)
if(!vis[i])
{
vis[i]=1;
father[i].to=0;
father[i].dist=-1;
dfs(i);
}
scanf("%d",&Q);
while(Q--)
{
int aa,bb;
scanf("%d%d",&aa,&bb);
printf("%d\n",lca(aa,bb));
}
return 0;
}