【NOIP2013提高組day1】貨車運輸

額呵呵，找到一個照片開始亂搞ing，（嘻嘻

前奏

讓我們進入正題，這道題目所涉知識面是很廣的，
先來列舉一下這道題的知識點:最小生成樹（最好是克魯斯卡爾，也就是說我們還要用到并查集）+LCA（最好是倍增的）+（鏈式前向星）
_{*其實我們這道題要應用的是最大生成樹，但是其實和最小生成樹差異不大，所以在后文我還是叫最小生成樹，}

所以對上面知識有問題的同學，建議去看一下以下文章：

最小生成樹詳細決議

鏈式前向星

倍增求LCA

LCA連我自己都還沒找到比較好的博客，所以，有時間自己復習梳理的時候寫一篇，

題目大意

給出你一幅圖和一些邊，每條邊有一些權值，兩兩城市間會有不止一條邊
問你從x城市到y城市的所有可行的路徑方案中，最小邊的最大值是多少
若兩城市不連通則輸出-1

對于 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，

題目解法

因為資料比較大，所以我們這題不講部分分，
因為直接暴力不是0分就是玄學水到20，
兩個步驟，最小生成樹+LCA（最近公共祖先）

最小生成樹

相對于prim,克魯斯卡爾會快一點，所以我們選擇性能優異的后者，而后者的思想主要是這樣的：
先排序，找到從小到大的權值的邊的序列，（因為是最大生成樹，所以這里是從大到小，
而我們要一個個去處理這些邊，如果這些邊的起始點和終點并不連接的話，我們就要保留這條邊，所以在這里我們要用到并查集，我們可以將進行合并操作，使得這棵樹的邊數最好縮小到節點數-1,而聯通所有的節點，

if(find(a[i].u)!=find(a[i].v))
	fa[find(a[i].u)]=find(a[i].v)

并且，我們在這里可以用到鏈式前向星存邊了，可以比矩陣快一點，

add(a[i].u,a[i].v,a[i].dis)

LCA

我們知道，這樣建出來的樹一定是可以求出符合題意答案的樹，所以我們直接考慮找答案，
為了讓我們的答案不讓別的因素影響，
舉個例子，如果多走了一條邊，這條邊的邊權比我們的答案要大，其實對我們的答案沒有影響，因為我們要選的答案是路徑上權值最小的一條邊，
如果這條邊的權值比我們的答案要小，其實對我們的答案還有不利影響，

這里講倍增的方法；
先預處理出每個節點的2的冪次祖先，然后在 O ( l o g ( n ) ) O(log(n)) O(log(n))的時間復雜度上求出路徑的極值，然后，我們就要用到一個很重要的式子，它的用處是轉移F陣列的值:
f [ x ] [ i ] = f [ f [ x ] [ i ? 1 ] ] [ i ? 1 ] ; f[x][i]=f[f[x][i-1]][i-1]; f[x][i]=f[f[x][i?1]][i?1];
然后，為了符合題意，我們就要求LCA中的最小值，
在倍增的方法中，我們需要選擇一種“跳”的方法，將兩個數的點跳到同一層，這樣可以使得我們求的LCA就是他們上一層的節點，
然后，我們還需要用到一個陣列來記錄一下就好了，

#include<bits/stdc++.h>
using namespace std;
int n,m,q,x,y;
int fa[10005];
int next[20005],first[20005],go[20005],dis[20005],tot;
int dep[10005],f[10005][30],fm[10005][30];
struct node{
	int u,v,dis;
}a[50005];
int read()
{
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9') x=x*10+s-'0',s=getchar();
	return x*f;
}
void qsort(int l,int r)
{
	int i=l,j=r,mid=a[(l+r)/2].dis;
	while(i<=j)
	{
		while(a[i].dis>mid) i++;
		while(a[j].dis<mid) j--;
		if(i<=j) swap(a[i],a[j]),i++,j--;
	}
	if(l<j) qsort(l,j);
	if(i<r) qsort(i,r);
}
void add(int u,int v,int len)//鏈式前向星 
{
	next[++tot]=first[u];first[u]=tot;go[tot]=v,dis[tot]=len;
	next[++tot]=first[v];first[v]=tot;go[tot]=u,dis[tot]=len;
}
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void ready(int o,int from)
{
	dep[o]=dep[from]+1;
	for(int i=1;i<=20;i++){
		f[o][i]=f[f[o][i-1]][i-1];
		fm[o][i]=min(fm[f[o][i-1]][i-1],fm[o][i-1]);
	}
	for(int i=first[o];i;i=next[i]){
		int v=go[i];
		if(v==from)continue;
		fm[v][0]=dis[i];
		f[v][0]=o;
		ready(v,o);
	}
}
int lca(int x,int y)
{
	int minx=0x7fffffff;
	if(dep[y]>dep[x]) swap(x,y);
	for(int i=20;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			minx=min(minx,fm[x][i]);
			x=f[x][i];
		}
		if(x==y) return minx; 
	}
	for(int i=20;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			minx=min(minx,min(fm[x][i],fm[y][i]));
			x=f[x][i];
			y=f[y][i];
		}
	}
	return min(minx,min(fm[x][0],fm[y][0]));
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i) fa[i]=i;
	for(int i=1;i<=m;++i) a[i].u=read(),a[i].v=read(),a[i].dis=read();
	qsort(1,m);
	for(int i=1;i<=m;++i)
		if(find(a[i].u)!=find(a[i].v))
			fa[find(a[i].u)]=find(a[i].v),add(a[i].u,a[i].v,a[i].dis);
	ready(1,0);
	q=read();
	for(int i=1;i<=q;++i)
	{
		x=read(),y=read();
		if(find(x)!=find(y)) printf("-1\n"); 
		else printf("%d\n",lca(x,y));
	}
	return 0;
}