5771. 【NOIP2008模拟】遨游

Description

MWH寒假外出旅游，来到了S国。S国划分为N个省，第i个省有Ti座城市，编号分别为Ci1，Ci2，……CiTi（各省城市编号不会重复）。所有城市间有M条双向的道路连接，从任意一个城市出发，可到达一切城市，每条道路均须收费。
此时恰逢春运期间，S国交通运输局采取了优惠措施。当一条路的路费在[L..R]区间时，可免去。同时，每个省也有优惠措施，第i个省内的每条道路路费收其Xi%，连接第i个省和第j个省的每条道路路费收其(Xi%+Xj%)/2。
MWH想从城市s走到城市t，请求出一对L，R，确保：

MWH能免费到达目的地；
L≤R；
L、R均为整数；
L尽可能地大，R在满足L最大的前提下最小。

注意：因每条道路由各省的交通运输局直接管辖，所以每条道路的路费必须先得到省级优惠，再得到国家级优惠。

Input

第一行两个整数N，M。
接下来M行，每行三个整数，u、v、w，表示连接u、v的道路需收费w。
接下来N行，第i+M+1行有一个整数Ti，后面Ti个整数，分别是Ci1..CiTi（所有城市编号保证按正整数顺序给出1.. $\sum$ Ti）。
下一行N个整数X1..Xi。
最后一行，两个整数，s、t。

Output

一行两个整数，如题，L和R。

Solutions

对于题目描述中既有“最大”又有“最小”的题目，很多都是用二分，这题也不例外。

首先，省级路费是很容易算且是独立的，所以预处理出每条道路经过了省级优惠后是多少路费。

接着，这题要用到二分嵌套。第一层是二分L（l,r,mid），第二层是二分R（l1,r1,mid1），中间要做一次搜索。把所有在[L..R]区间内的边取出，做一遍搜索，如果能到达目的地则记录mid1，并将r1改小，否则将l1改大。第一重二分中如果能取到mid1则记录下mid与mid1，并将l1改大，否则将r1改小。

代码

  1 type
  2   arr=record
  3     y,next:longint;
  4     w:real;
  5   end;
  6 var
  7   n,m,nm,qq,zz,maxl,maxr:longint;
  8   a:array [0..400001] of arr;
  9   ls,list,v,bo:array [0..400001] of longint;
 10   b,bz:array [0..50001] of longint;
 11 
 12 procedure add(x,y:longint;z:real);
 13 begin
 14   inc(nm);
 15   a[nm].y:=y; a[nm].w:=z;
 16   a[nm].next:=ls[x]; ls[x]:=nm;
 17 end;
 18 
 19 procedure init;
 20 var
 21   i,j,t,k:longint;
 22   x,y:array [0..200001] of longint;
 23   z:array [0..200001] of real;
 24 begin
 25   readln(n,m);
 26   nm:=0;
 27   for i:=1 to m do
 28     readln(x[i],y[i],z[i]);
 29   for i:=1 to n do
 30     begin
 31       read(t);
 32       for j:=1 to t do
 33         begin
 34           read(k);
 35           b[k]:=i;
 36         end;
 37     end;
 38   for i:=1 to n do
 39     read(bz[i]);
 40   readln(qq,zz);
 41   for i:=1 to m do
 42     begin
 43       if b[x[i]]=b[y[i]] then z[i]:=z[i]*bz[b[x[i]]]/100
 44                          else z[i]:=z[i]*(bz[b[x[i]]]+bz[b[y[i]]])/200;
 45       add(x[i],y[i],z[i]);
 46       add(y[i],x[i],z[i]);
 47     end;
 48 end;
 49 
 50 function max(o,p:real):real;
 51 begin
 52   if o>p then exit(o);
 53   exit(p);
 54 end;
 55 
 56 function min(o,p:real):real;
 57 begin
 58   if o<p then exit(o);
 59   exit(p);
 60 end;
 61 
 62 function bfs1(ll:longint):boolean;
 63 var
 64   i,j,k,h,t:longint;
 65 begin
 66   fillchar(bo,sizeof(bo),0);
 67   fillchar(v,sizeof(v),0);
 68   fillchar(list,sizeof(list),0);
 69   h:=0; t:=1;
 70   v[qq]:=1; list[1]:=qq; bo[qq]:=1;
 71   repeat
 72     h:=h+1;
 73     j:=ls[list[h]];
 74     while j<>0 do
 75       begin
 76         with a[j] do
 77           begin
 78             if w-ll>=0 then
 79               begin
 80                 if bo[y]=0 then
 81                   begin
 82                     bo[y]:=1;
 83                     if v[y]=0 then
 84                       begin
 85                         t:=t+1;
 86                         list[t]:=y;
 87                         v[y]:=1;
 88                       end;
 89                   end;
 90               end;
 91             j:=next;
 92           end;
 93       end;
 94     v[list[h]]:=0;
 95   until h=t;
 96   if bo[zz]=1 then exit(true)
 97               else exit(false);
 98 end;
 99 
100 function bfs2(ll:longint):boolean;
101 var
102   i,j,k,h,t:longint;
103 begin
104   fillchar(bo,sizeof(bo),0);
105   fillchar(v,sizeof(v),0);
106   fillchar(list,sizeof(list),0);
107   h:=0; t:=1;
108   v[qq]:=1; list[1]:=qq; bo[qq]:=1;
109   repeat
110     h:=h+1;
111     j:=ls[list[h]];
112     while j<>0 do
113       begin
114         with a[j] do
115           begin
116             if (ll-w>=0) and (w-maxl>=0)  then
117               begin
118                 if bo[y]=0 then
119                   begin
120                     bo[y]:=1;
121                     if v[y]=0 then
122                       begin
123                         t:=t+1;
124                         list[t]:=y;
125                         v[y]:=1;
126                       end;
127                   end;
128               end;
129             j:=next;
130           end;
131       end;
132     v[list[h]]:=0;
133   until h=t;
134   if bo[zz]=1 then exit(true)
135               else exit(false);
136 end;
137 
138 procedure main;
139 var
140   l,r,mid:longint;
141 begin
142   l:=0; r:=maxlongint div 30;
143   while l<=r do
144     begin
145       mid:=(l+r) div 2;
146       if bfs1(mid) then
147         begin
148           maxl:=mid; l:=mid+1;
149         end else r:=mid-1;
150     end;
151   l:=0; r:=maxlongint div 30;
152   while l<=r do
153     begin
154       mid:=(l+r) div 2;
155       if bfs2(mid) then
156         begin
157           maxr:=mid; r:=mid-1;
158         end else l:=mid+1;
159     end;
160   writeln(maxl,' ',maxr);
161 end;
162 
163 begin
164   assign(input,'trip.in');
165   assign(output,'trip.out');
166   reseT(input);
167   rewrite(output);
168   init;
169   main;
170   close(input);
171   close(output);
172 end.