亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

wiki 2490 導彈攔截塔

系統 2257 0

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 導彈攔截塔


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 一区二区三区在线免费 | 黄色免费在线观看 | 一级毛片在线视频 | 欧美激情一区二区三区视频 | 亚洲国产精久久久久久久春色 | 日韩男女视频 | 国模私拍视频在线 | 日本精品视频一视频高清 | 一区二区三区在线观看视频 | 草久久免费视频 | 欧美13一14周岁a在线播放 | 国产日韩一区二区三区在线观看 | a级毛片免费 | 护士日本xxxxx丰满hd4k | 日本高清不卡网站免费 | 天天干夜夜看 | 久久93精品国产91久久综合 | 亚洲欧美一区二区三区在线 | 日本 亚洲 欧美 | 国产在线精品一区二区中文 | 免费看美女隐私的网站 | 欧美熟videos肥婆 | 爆操白虎 | 国产一区二区成人 | 国产乱码一区二区三区 | 亚洲成年网 | 中文字幕免费在线视频 | 天天综合天天 | 国产精品亚洲成在人线 | 性xxx免费视频 | 日本a一级毛片免费观看 | 四虎884| 99视频全部免费精品全部四虎 | 羞羞视频免费网站 | 日韩在线a视频免费播放 | 中文字幕日韩在线观看 | 国产精品伦视频观看免费 | 国产婷婷丁香久久综合 | 青青久久精品国产免费看 | 精品国产成人综合久久小说 | 国产大尺度福利视频在线观看 |