3287 货车运输
2013年NOIP全国联赛提高组
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出共有 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。
分类标签 Tags 点此展开
题解：本来想把这道题当作个娱乐的，可是一写就逗比了，然后疯狂查错，查得要疯了——结果发现一开始快排写错了（HansBug：巨汗*_* phile：我也是醉疯了）
别的不难，思路就是——先最大生成树，然后每次只要访问在这棵树上面的路径的瓶颈值即可，我用了下lca算法，可是看样子时间相当之充裕让我都吓了一跳，所以估计就算是暴力找路的话估计也能差不多AC么么哒
type
point=^node;
node=record
g,w:longint;
next:point;
end;
var
i,j,k,l,m,n,tt,t,yy:longint;
a:array[..,..] of longint;
c,ct,f:array[..] of longint;
d,e:array[..,..] of longint;
b:array[..] of point;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function getfat(x:longint):longint;
begin
if x<>c[x] then c[x]:=getfat(c[x]);
exit(c[x]);
end;
procedure merge(x,y:longint);
var a1,a2:longint;
begin
a1:=getfat(x);a2:=getfat(y);
if a1=a2 then exit;
c[getfat(x)]:=getfat(y);
dec(tt);
end;
function tog(x,y:longint):boolean;
begin
exit(getfat(x)=getfat(Y));
end;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=a[(l+r) div ,];
repeat
while a[i,]>x do inc(i);
while a[j,]<x do dec(j);
if i<=j then
begin
swap(a[i,],a[j,]);
swap(a[i,],a[j,]);
swap(a[i,],a[j,]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure add(x,y,z:longint);
var p:point;
begin
new(p);
p^.w:=z;p^.g:=y;
p^.next:=b[x];b[x]:=p;
end;
procedure dfs(x:longint);
var p:point;
begin
p:=b[x];
while p<>nil do
begin
if d[,p^.g]= then
begin
d[,p^.g]:=x;
e[,p^.g]:=p^.w;
f[p^.g]:=f[x]+;
dfs(p^.g);
end;
p:=p^.next;
end;
end;
function fatfat(x,y:longint):longint;
var i,j:longint;
begin
i:=;
while y> do
begin
if odd(y) then x:=d[i,x];
inc(i);y:=y div ;
end;
exit(x);
end;
function fatlen(x,y:longint):longint;
var i,j:longint;
begin
i:=;j:=maxlongint;
while y> do
begin
if odd(y) then
begin
j:=min(j,e[i,x]);
x:=d[i,x];
end;
inc(i);y:=y div ;
end;
exit(j);
end;
function getlent(x,y:longint):longint;
var a1,a2,a3,a4,i:longint;
begin
if c[x]<>c[y] then exit(-);
if f[x]<f[y] then swap(x,y);
a3:=x;a4:=y;
x:=fatfat(x,f[x]-f[y]);
if x=y then exit(fatlen(a3,f[a3]-f[a4]));
for i:= downto do
begin
if not((d[i,x]=) or (d[i,x]=d[i,y])) then
begin
x:=d[i,x];
y:=d[i,y];
end;
end;
a1:=d[,x];
exit(min(fatlen(a4,f[a4]-f[a1]),fatlen(a3,f[a3]-f[a1])));
end;
begin
readln(n,m);
for i:= to m do readln(a[i,],a[i,],a[i,]);
sort(,m);
FOR I:= to n do c[i]:=i;
tt:=n;
for i:= to m do
merge(a[i,],a[i,]);
for i:= to n do c[i]:=i;
for i:= to n do b[i]:=nil;
j:=;
fillchar(d,sizeof(d),);yy:=tt;
for i:= to n-yy do
begin
inc(j);
while tog(a[j,],a[j,]) do inc(j);
add(a[j,],a[j,],a[j,]);
add(a[j,],a[j,],a[j,]);
merge(a[j,],a[j,]);
end;
for i:= to n do c[i]:=getfat(c[i]);
fillchar(ct,sizeof(ct),);
fillchar(f,sizeof(f),);
for i:= to n do
begin
if ct[c[i]]= then
begin
ct[c[i]]:=;
d[,i]:=-;
dfs(i);
d[,i]:=;
end;
end;
for i:= to do
for j:= to n do
begin
d[i,j]:=d[i-,d[i-,j]];
if (e[i-,d[i-,j]]<>) and (e[i-,j]<>) then
e[i,j]:=min(e[i-,d[i-,j]],e[i-,j])
else
begin
if e[i-,d[i-,j]]= then
begin
if e[i-,j]= then
e[i,j]:=maxlongint
else
e[i,j]:=e[i-,j] end
else
e[i,j]:=e[i-,d[i-,j]];
end;
end;
readln(t);
for i:= to t do
begin
readln(j,k);
writeln(getlent(j,k));
end;
readln;
end.