[NOIP2013]货车运输

Posted by Cww97 on 2015-11-25
  • 时间限制: 1 s
    • 空间限制: 128000 KB
    • 题目等级 : 钻石 Diamond. 题目描述 Description
      A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入描述 Input Description
第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意:x 不等于 y。

输出描述 Output Description
输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。

样例输入 Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 Sample Output
3
-1
3

数据范围及提示 Data Size & Hint
对于 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。

kruskal最大生成树+倍增
【code】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
program cx;
uses math;
var i,m,n,sa,tg,treenum,cnt,qq,t:longint;
home,ax,ay,aw,gym,head,next,e,w,h:array[0..100000]of longint;
q:array[0..1000000]of longint;
v:array[0..100000]of boolean;
f,g:array[0..10000,0..20]of longint;

function find(x:longint):longint;
begin
if home[x]=x then exit(x);
home[x]:=find(home[x]);
exit(home[x]);
end;

procedure link(x,y,z:longint);
begin
inc(cnt); e[cnt]:=y; w[cnt]:=z;
next[cnt]:=head[x]; head[x]:=cnt;
end;

procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l; j:=r;
x:=aw[(l+r) >>1];
repeat
while aw[i]<x do inc(i);
while x<aw[j] do dec(j);
if not(i>j) then
begin
y:=aw[i]; aw[i]:=aw[j]; aw[j]:=y;
y:=ax[i]; ax[i]:=ax[j]; ax[j]:=y;
y:=ay[i]; ay[i]:=ay[j]; ay[j]:=y;
inc(i); j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

procedure kruskal;
var i,tot:longint;
begin
fillchar(v,sizeof(v),0);
for i:=1 to n do
if not v[find(i)] then
begin inc(treenum); v[find(i)]:=true; end;
for i:=1 to n do home[i]:=i;
sort(1,m);
tot:=0;
for i:=m downto 1 do
begin
if find(ax[i])=find(ay[i]) then continue;
home[find(ax[i])]:=find(ay[i]);
link(ax[i],ay[i],aw[i]);
link(ay[i],ax[i],aw[i]);
inc(tot);
if tot=n-treenum then break;
end;
end;

procedure dfs(x:longint);
var i,t:longint;
begin
v[x]:=true;
for i:=1 to 17 do
begin
if h[x]<(1<<i) then break;
f[x,i]:=f[f[x,i-1],i-1];
g[x,i]:=min(g[x,i-1],g[f[x,i-1],i-1]);
end;
t:=head[x];
while t>0 do
begin
if not v[e[t]] then
begin
f[e[t],0]:=x;
g[e[t],0]:=w[t];
h[e[t]]:=h[x]+1;
dfs(e[t]);
end;
t:=next[t];
end;
end;

function lca(x,y:longint):longint;
var i,t:longint;
begin
if h[x]<h[y] then begin t:=x; x:=y; y:=t; end;
t:=h[x]-h[y];
for i:=0 to 17 do
if not (((1<<i) and t)=0) then
x:=f[x,i];
if x=y then exit(x);
for i:=17 downto 0 do
if f[x,i]<>f[y,i] then
begin x:=f[x,i]; y:=f[y,i]; end;
if x=y then exit(x);
exit(f[x,0]);
end;

function ask(x,y:longint):longint;
var i,hk,t:longint;
begin
hk:=maxlongint;
t:=h[x]-h[y];
for i:=0 to 17 do
if not ((1<<i)and t=0) then
begin
hk:=min(hk,g[x,i]);
x:=f[x,i];
end;
exit(hk);
end;

begin
ASSIGN(INPUT, 'truck.in'); RESET(INPUT);
ASSIGN(OUTPUT,'truck.out');REWRITE(OUTPUT);
read(n,m);
for i:=1 to n do home[i]:=i;
for i:=1 to m do
begin
read(ax[i],ay[i],aw[i]);
home[find(ax[i])]:=find(ay[i]);
end;
kruskal;

fillchar(v,sizeof(v),0);
for i:=1 to n do
if not v[i] then dfs(i);
read(qq);
for i:=1 to qq do
begin
read(sa,tg);
if find(sa)<>find(tg) then writeln(-1)
else begin
t:=lca(sa,tg);
writeln(min(ask(sa,t),ask(tg,t)));
end;
end;
CLOSE(INPUT);
CLOSE(OUTPUT);
end.