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.
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
