3732: Network
3732: Network
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 395 Solved: 179
Description
给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。 图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 15,000)。 每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Input
第一行： N, M, K。 第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。 第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Output
对每个询问，输出最长的边最小值是多少。
Sample Input
6 6 8 1 2 5 2 3 4 3 4 3 1 4 8 2 5 7 4 6 2 1 2 1 3 1 4 2 3 2 4 5 1 6 2 6 1
Sample Output
5 5 5 4 4 7 4 5
HINT
1 <= N <= 15,000 1 <= M <= 30,000 1 <= d_j <= 1,000,000,000 1 <= K <= 15,000
Source
题解：简直逗比到家啊——昨天我的程序先是TLE，但是一想这个复杂度应该不会啊，感觉不对头，于是发现了数组开小了（phile：数组开小怎么会TLE？ HansBug：我哪知道= =）然后再交就WA，不停的WA，我硬是找了一个晚上的错，结果啥都没弄出来，还是那样，弃疗了，向lydsy2012要了下数据。。。今天数据到手，手工一测试，怎么测都没错？！？！然后再Submit一次一个字都没动的程序，Accept（HansBug：这。。。）。。。好了说思路——这题可以算是NOIP2013货车运输的修改+略微强化版，先是求出最小生成树（额。。我一般用并查集+kruskal），然后DFS建树，然后用倍增进行O(nlogn)的初始化，然后每次一个O(logn)地求LCA（至于路径上的最大值嘛，只要再加一个数组就行啦），就这样O(nlogn)地AC之。。。（HansBug：不过这个逗比的Judge还是害得我纠结了一晚上啊TT phile：不是和你说了嘛变量不清零有时候会跪掉。。。 HansBug：GET IT。。。）
1 type
2 point=^node;
3 node=record
4 w,g:longint;
5 next:point;
6 end;
7
8 var
9 i,j,k,l,m,n,t:longint;
10 a:array[0..40000] of point;
11 b:array[0..40000,1..3] of longint;
12 c,f,g,h:array[0..40000] of longint;
13 d:array[0..20,0..40000] of longint;
14 e:array[0..20,0..40000] of longint;
15 function getfat(x:longint):longint;inline;
16 begin
17 while x<>c[x] do x:=c[x];
18 getfat:=x;
19 end;
20 function tog(x,y:longint):boolean;inline;
21 begin
22 exit(getfat(x)=getfat(y));
23 end;
24 procedure merge(x,y:longint);inline;
25 begin
26 c[getfat(x)]:=getfat(y);
27 end;
28
29 procedure add(x,y,z:longint);inline;
30 var p:point;
31 begin
32 new(p);
33 p^.g:=y;
34 p^.w:=z;
35 p^.next:=a[x];
36 a[x]:=p;
37 end;
38 procedure swap(var x,y:longint);inline;
39 var z:longint;
40 begin
41 z:=x;x:=y;y:=z;
42 end;
43 procedure sort(l,r:longint);inline;
44 var i,j,x,y:longint;
45 begin
46 i:=l;j:=r;x:=b[(l+r) div 2,3];
47 repeat
48 while b[i,3]<x do inc(i);
49 while b[j,3]>x do dec(j);
50 if i<=j then
51 begin
52 swap(b[i,1],b[j,1]);
53 swap(b[i,2],b[j,2]);
54 swap(b[i,3],b[j,3]);
55 inc(i);dec(j);
56 end;
57 until i>j;
58 if l<j then sort(l,j);
59 if i<r then sort(i,r);
60 end;
61 procedure dfs(x:longint);inline;
62 var p:point;
63 begin
64 p:=a[x];
65 while p<>nil do
66 begin
67 if d[0,p^.g]=0 then
68 begin
69 d[0,p^.g]:=x;
70 e[0,p^.g]:=p^.w;
71 c[p^.g]:=c[x]+1;
72 dfs(p^.g);
73 end;
74 p:=p^.next;
75 end;
76 end;
77 function max(x,y:longint):longint;inline;
78 begin
79 if x>y then max:=x else max:=y;
80 end;
81 function fatget(x,y:longint):longint;//inline;
82 var i:longint;
83 begin
84 i:=0;
85 while y>0 do
86 begin
87 if odd(y) then x:=d[i,x];
88 inc(i);
89 y:=y div 2;
90 end;
91 exit(x);
92 end;
93 function getmax(x,y:longint):longint;//inline;
94 var i,j:longint;
95 begin
96 i:=0;j:=0;
97 while y>0 do
98 begin
99 if odd(y) then
100 begin
101 j:=max(j,e[i,x]);
102 x:=d[i,x];
103 end;
104 inc(i);
105 y:=y div 2;
106 end;
107 exit(j);
108 end;
109 function getcom(x,y:longint):longint;//inline;
110 var i,j,k,l:longint;
111 begin
112 if x=y then exit(x);
113 if c[x]<c[y] then swap(x,y);
114 x:=fatget(x,c[x]-c[y]);
115 if x=y then exit(x);
116 i:=20;
117 while i>=0 do
118 begin
119 if d[i,x]<>d[i,y] then
120 begin
121 x:=d[i,x];
122 y:=d[i,y];
123 end;
124 dec(i);
125 end;
126 exit(d[0,x]);
127 end;
128 function getpath(x,y:longint):longint;//inline;
129 var i,j,k,l:longint;
130 begin
131 l:=getcom(x,y);
132 getpath:=max(getmax(x,c[x]-c[l]),getmax(y,c[y]-c[l]));
133 end;
134
135 begin
136 readln(n,m,t);
137 for i:=1 to n do a[i]:=nil;
138 for i:=1 to n do c[i]:=i;
139 for i:=1 to m do
140 readln(b[i,1],b[i,2],b[i,3]);
141 sort(1,m);
142 j:=1;
143 for i:=1 to n-1 do
144 begin
145 while tog(b[j,1],b[j,2]) do inc(j);
146 add(b[j,1],b[j,2],b[j,3]);
147 add(b[j,2],b[j,1],b[j,3]);
148 merge(b[j,1],b[j,2]);
149 end;
150 fillchar(d,sizeof(d),0);
151 fillchar(c,sizeof(c),0);
152 d[0,1]:=-1;
153 dfs(1);
154 d[0,1]:=0;
155 for i:=1 to 20 do
156 begin
157 for j:=1 to n do
158 begin
159 d[i,j]:=d[i-1,d[i-1,j]];
160 e[i,j]:=max(e[i-1,d[i-1,j]],e[i-1,j]);
161 end;
162 end;
163 for i:=1 to t do
164 begin
165 readln(j,k);
166 writeln(getpath(j,k));
167 end;
168 end.
169 腾讯云开发者
