首页 > 代码库 > 3732: Network
3732: Network
3732: Network
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
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
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) then100 begin101 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 begin112 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 do118 begin119 if d[i,x]<>d[i,y] then120 begin121 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 begin131 l:=getcom(x,y);132 getpath:=max(getmax(x,c[x]-c[l]),getmax(y,c[y]-c[l]));133 end;134 135 begin136 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 do140 readln(b[i,1],b[i,2],b[i,3]);141 sort(1,m);142 j:=1;143 for i:=1 to n-1 do144 begin145 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 do156 begin157 for j:=1 to n do158 begin159 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 do164 begin165 readln(j,k);166 writeln(getpath(j,k));167 end;168 end.169
3732: Network
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。