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.

wiki 2490 導彈攔截塔