记录编号	269514	评测结果	TTTTTTTTTT
题目名称	[USACO Oct08] 挖水井	最终得分	0
用户昵称	安呐一条小咸鱼。	是否通过	未通过
代码语言	C++	运行时间	10.010 s
提交时间	2016-06-13 17:44:38	内存使用	2.67 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10010;
int n,m,r1,r2,ask,x,y,t;
int father[maxn],Deep[maxn];
//并查集判断是否连通 用来输出-1； 
int mind[maxn][20],f[maxn][20];
//类似dp的 统计x与y之间路径的最小值 ； 
/*
开一个数组f[i][j]，来表示i 点的2j 祖先那么f[i][0] 就
表示i 的父亲节点。
f[i][j] = f[ f[i][j-1] ][j-1]
i 点的2j .. 1 祖先的2j .. 1 祖先就是i 点的2j 祖先。
*/ 
int head[maxn<<2],tot=0;
inline int Read() 
{
	int ret;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	ret=ch-'0';
	ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		ret=ret*10+ch-'0';
		ch=getchar();
	}
	return ret;
}
int find(int x)
{
	if(father[x]!=x)
	{
		father[x]=find(father[x]);
	}
	return father[x];
}
inline bool unionn(int x,int y)
{
	r1=find(x);
	r2=find(y);
	if(r1==r2)return false;//已经合并 false
	else 
	{
		father[r2]=r1;
		return true;
	}
}
class Node
{
	public:
	    int to,next,v;
}edge[maxn<<2];
struct tree
{
	int s,t,v;
}Tree[maxn<<2];
inline bool comp(const tree &a,const tree &b)
{
	return a.v>=b.v;
}
void Addedge(int x,int y,int v)
{
	edge[++tot].to=y;
	edge[tot].v=v;
	edge[tot].next=head[x];
	head[x]=tot;
}
void Build(int x,int deep)
{
	Deep[x]=deep;//更新deep 
	for(int i=head[x];i!=0;i=edge[i].next)
	{
		int cy=edge[i].to; 
		if(!f[cy][0])//
		{
			f[cy][0]=x;
			mind[cy][0]=edge[i].v;
			Build(cy,deep+1);
		}
	}
}
inline int Lca(int x,int y)
/*
要找到距离i 节点最远的祖先：for (int j = 20;j >= 0;j --)
if (f[i][j]) i = f[i][j] ;
		__O(log2n)__
上翻法把x 调到与y 相同的深度，此时
若x == y 那么此时的x 或y 就是他们的LCA
否则，接下来同时把x 和y 向上翻，直到f[x][0] == f[y][0], 此
时的fa[x][0] 就是LCA 。
*/ 
{
	int ret=0x7fffffff;
	if(Deep[x]<Deep[y])swap(x,y);
	for(int i=t;i>=0;i--)
	{
		if( Deep[ f[x][i] ]>=Deep[y])
		{
			ret=min(ret,mind[x][i]);
			x=f[x][i];
		}
	}
	if(x!=y)
	{
		for(int i=t;i>=0;i--)
		{
			if(f[x][i]!=f[y][i])
			{
				ret=min( ret ,  min( mind[x][i],mind[y][i] ) );
				x=f[x][i];
				y=f[y][i];
			}
		}
		ret=min( ret ,  min( mind[x][0],mind[y][0] ) );
	}
	return ret;
}
int main()
{
	freopen("truck.in","r",stdin);freopen("truck.out","w",stdout);
	n=Read();
	m=Read();
	for(int i=1;i<=n;i++)
	{
		father[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		Tree[i].s=Read();
		Tree[i].t=Read();
		Tree[i].v=Read();
	}
	sort(Tree+1,Tree+m+1,comp);//按载重排序； 
	for(int i=1;i<=m;i++)
	{
		if(unionn(Tree[i].s,Tree[i].t))//没有连接；加边； 
		{
			Addedge(Tree[i].s,Tree[i].t,Tree[i].v);
			Addedge(Tree[i].t,Tree[i].s,Tree[i].v);
		}
	}
	t=log(  (2*n-1)*1.0  )/log(2.0);
	for(int i=1;i<=t;i++)//初始化； 
	{
		if(!f[i][0])
		{
			f[i][0]=i;
			mind[i][0]=0x7fffffff;
			Build(i,1);//从deep=1开始向下搜。 
		}
	}
	for(int j=1;j<=t;j++)
	{
		for(int i=1;i<=n;i++)
		{
			f[i][j]=f[ f[i][j-1] ][j-1];//i点的2^j-1祖先的2^j-1祖先就是i点的2^j祖先
			mind[i][j]=min(mind[i][j-1],mind[ f[i][j-1] ][j-1]);
			/*
			对于此类问题，由于我们只关注最大（最小）的那条边，那么我们可以先sort一遍，然后像Kruskar一样加边，
			此时我们查询x，y之间的最值只需要统计树上x与y之间路径的最小值即可，用倍增LCA
			*/
		} 
	}
	ask=Read();
	for(int i=1;i<=ask;i++)
	{
		x=Read();
		y=Read();
		if(find(x)!=find(y))puts("-1");//没有连接 直接输出-1；
		else
		{
			printf("%d\n",Lca(x,y));
		} 
	}
	return 0;
}