首页 > 代码库 > 1602: [Usaco2008 Oct]牧场行走
1602: [Usaco2008 Oct]牧场行走
1602: [Usaco2008 Oct]牧场行走
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1211 Solved: 616
[Submit][Status]
Description
N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
Input
*第一行：两个被空格隔开的整数：N和Q
*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI
*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。
Output
*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。
Sample Input
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
Sample Output
2
7
HINT
Source
资格赛
题解：这是一个还算比较裸的LCA（最近公公祖先问题），我用的是倍增算法（初始化O(nlogn)，每次查询O(nlogn)）然后只要用一个DFS建树，然后A之（以前一直以为DFS建树绝对会爆掉，但仔细一想DFS复杂度只要用邻接表存储最初的图的话，不过才O(2n)而已）
1 type 2 point=^node; 3 node=record 4 g,w:longint; 5 next:point; 6 end; 7 8 var 9 i,j,k,l,m,n:longint; 10 a,b:array[0..15,0..15000] of longint; 11 c:array[0..15000] of point; 12 d:array[0..15000] of longint; 13 procedure swap(var x,y:longint); 14 var z:longint; 15 begin 16 z:=x;x:=y;y:=z; 17 end; 18 procedure add(x,y,z:longint); 19 var 20 p:point; 21 begin 22 new(p); 23 p^.w:=z; 24 p^.g:=y; 25 p^.next:=c[x]; 26 c[x]:=p; 27 end; 28 procedure dfs(x:longint); 29 var 30 p:point; 31 begin 32 p:=c[x]; 33 while p<>nil do 34 begin 35 if d[p^.g]=0 then 36 begin 37 d[p^.g]:=d[x]+1; 38 a[0,p^.g]:=x; 39 b[0,p^.g]:=p^.w; 40 dfs(p^.g); 41 end; 42 p:=p^.next; 43 end; 44 end; 45 function getfat(x,y:longint):longint; 46 var i:longint; 47 begin 48 i:=0; 49 while y>0 do 50 begin 51 if odd(y) then x:=a[i,x]; 52 inc(i); 53 y:=y div 2; 54 end; 55 exit(x); 56 end; 57 function getcom(x,y:longint):longint; 58 var i,j:longint; 59 begin 60 if d[x]<d[y] then swap(x,y); 61 x:=getfat(x,d[x]-d[y]); 62 if x=y then exit(x); 63 i:=15; 64 while i>=0 do 65 begin 66 if a[i,x]<>a[i,y] then 67 begin 68 x:=a[i,x]; 69 y:=a[i,y]; 70 end; 71 dec(i); 72 end; 73 exit(a[0,x]); 74 end; 75 function getsum(x,y:longint):longint; 76 var i,j,k:longint; 77 begin 78 i:=0;j:=0; 79 while y>0 do 80 begin 81 if odd(y) then 82 begin 83 j:=j+b[i,x]; 84 x:=a[i,x]; 85 end; 86 y:=y div 2; 87 inc(i); 88 end; 89 exit(j); 90 end; 91 begin 92 readln(n,m); 93 for i:=1 to n do c[i]:=nil; 94 for i:=1 to n-1 do 95 begin 96 readln(j,k,l); 97 add(j,k,l); 98 add(k,j,l); 99 end;100 fillchar(d,sizeof(d),0);101 d[1]:=1;102 dfs(1);103 104 for i:=1 to 15 do105 for j:=1 to n do106 a[i,j]:=a[i-1,a[i-1,j]];107 108 for i:=1 to 15 do109 for j:=1 to n do110 b[i,j]:=b[i-1,j]+b[i-1,a[i-1,j]];111 112 for i:=1 to m do113 begin114 readln(j,k);115 l:=getcom(j,k);116 writeln(getsum(j,d[j]-d[l])+getsum(k,d[k]-d[l]));117 end;118 end.
1602: [Usaco2008 Oct]牧场行走
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。