P1967 货车运输
最大生成树+lca+并查集

 #include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.11.8
using namespace std;
int n,m,q;
int x,y,z;
int cnt;
int Min[][];
int f[][];
int d[];
int deep[]; struct kru
{
int l,r,v;
bool operator<(const kru&a)const
{
return v>a.v;
}
}E[]; struct node
{
int n;
int v;
node *next;
}*e[]; inline void in(register int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=(x<<)+(x<<)+c-'',c=g();
x*=y;
}
inline void o(register int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} inline int find(register int x)
{
if(d[x]==x)return x;
d[x]=find(d[x]);
return d[x];
} inline void push(register int x,register int y,register int v)
{
node *p;
p=new node();
p->n=y;
p->v=v;
if(e[x]==NULL)
e[x]=p;
else
{
p->next=e[x]->next;
e[x]->next=p;
}
} inline void build(register int now)
{
deep[now]=deep[f[now][]]+;
for(register int i=;(<<i)<=n;i++)
{
Min[now][i]=min(Min[now][i-],Min[f[now][i-]][i-]);
f[now][i]=f[f[now][i-]][i-];
}
for(node *i=e[now];i!=NULL;i=i->next)
{
if(i->n!=f[now][])
{
f[i->n][]=now;
Min[i->n][]=i->v;
build(i->n);
}
}
} int query(int x,int y)
{
int MIN=inf;
if(deep[x]<deep[y])
swap(x,y);
int c=deep[x]-deep[y];
for(register int i=;(<<i)<=c;i++)
if((<<i)&c)
{
MIN=min(MIN,Min[x][i]);
x=f[x][i];
}
if(x==y)
return MIN;
c=log2(deep[x]);
for(register int i=c;i>=;i--)
{
if(f[x][i]!=f[y][i])
{
MIN=min(MIN,Min[x][i]);
MIN=min(MIN,Min[y][i]);
x=f[x][i];
y=f[y][i];
}
}
return min(MIN,min(Min[y][],Min[x][]));
} int main()
{
in(n),in(m);
For(i,,n)
d[i]=i;
For(i,,m)
in(E[i].l),in(E[i].r),in(E[i].v);
sort(E+,E+m+);
For(i,,m)
{
if(find(E[i].l)!=find(E[i].r))
{
d[find(E[i].l)]=find(E[i].r);
cnt++;
push(E[i].l,E[i].r,E[i].v);
push(E[i].r,E[i].l,E[i].v);
}
if(cnt==n-)
break;
}
Min[][]=inf;
build();
in(q);
For(i,,q)
{
in(x),in(y);
if(find(x)!=find(y))
o(-),p('\n');
else
o(query(x,y)),p('\n');
}
return ;
}
04-27 18:10