wiki 2490 导弹拦截塔
2013-09-23 21:16
二分答案+匈牙利判断
对于每一个时间，我们重新建一张二分图，由于每个塔可能打多次，所以要拆点，
对于每个拆的点的可行飞行距离为(mid-t1)-(ll-1)*(t1+t2)*v，其中mid为二分的答案
ll为将当前的点拆成第几个点（因为拆的点的时间是不一样的），然后依次判断该点和
入侵者的距离是否小于，是则加边。
建完图之后判断是否存在完美匹配，存在则向下二分，否则向上二分。
//吐槽下，靠靠，t1的单位是秒，t2的单位是分钟。。。
代码只是过了数据，好多地方都可以优化。
比较弱，二分没有标程写的好，标程可以直接得到最后答案。
//By BLADEVIL
var
n, m, t2, v :longint;
t1 :real;
dis :array[0..100,0..100] of real;
ans :real;
pre, other, last :array[0..200100] of longint;
link :array[0..100] of longint;
flag :array[0..100] of boolean;
x1, x2, y1, y2 :array[0..100] of longint;
l :longint;
len :array[0..200100] of real;
procedure init;
var
i, j :longint;
begin
read(n,m,t1,t2,v);
for i:=1 to m do read(x2[i],y2[i]);
for i:=1 to n do read(x1[i],y1[i]);
t1:=t1/60;
for i:=1 to n do
for j:=1 to m do
dis[i,j]:=sqrt((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j]));
end;
procedure connect(x,y:longint; z:real);
begin
inc(l);
pre[l]:=last[x];
last[x]:=l;
other[l]:=y;
len[l]:=z;
end;
function find(i:longint):boolean;
var
q, p :longint;
begin
q:=last[i];
while q<>0 do
begin
p:=other[q];
if (not flag[p]) then
begin
flag[p]:=true;
if (link[p]=0) or (find(link[p])) then
begin
link[p]:=i;
exit(true);
end;
end;
q:=pre[q];
end;
exit(false);
end;
procedure judge(low,high:real);
var
mid :real;
tot :longint;
i, j, ll :longint;
k :longint;
count :longint;
begin
if high<low then exit;
fillchar(last,sizeof(last),0);
fillchar(link,sizeof(link),0);
tot:=0;
l:=1;
mid:=(low+high)/2;
k:=trunc(((mid-t1)/(t1+t2))+1);
for i:=1 to n do
for ll:=1 to k do
begin
inc(tot);
for j:=1 to m do
if (((mid-t1)-(ll-1)*(t1+t2))*v)>=dis[i,j]
then connect(tot,j,dis[i,j]/v+(ll-1)*(t1+t2)+t1);
end;
count:=0;
for i:=1 to tot do
begin
fillchar(flag,sizeof(flag),false);
if find(i) then inc(count);
end;
if (high-low<1e-8) then
if count>=m then
begin
ans:=mid;
end else exit;
if count>=m then
begin
ans:=mid;
judge(low,mid-1e-8);
end else judge(mid+1e-8,high);
end;
procedure main;
begin
judge(1,30000);
writeln(ans:0:6);
end;
begin
init;
main;
end.