3732: Network

浏览数：39 / 时间：2015年06月09日

3732: Network

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 395 Solved: 179
[Submit][Status]

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货车运输的修改+略微强化版，先是求出最小生成树（额。。我一般用并查集写prim），然后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