題面

【正解】

一眼不可做啊

……相當于求路線上穿過的點最小距離最大

最小最大……二分啊

現在相當于給一個直徑，要判斷這個直徑是否能從左邊穿到右邊

我們可以在距離不超過直徑的點連一條邊，\(y=0\)和\(y=L\)建虛點，然后判斷他們是否連通，如果連通說明不能通過

復雜度\(O(N^2 log(L/eps))\)

實際上，這就是求兩個虛點的最小瓶頸路的過程

也可以跑一遍最小生成樹，在連通的時候輸出加上的那條邊

復雜度\(O(N^2 log(N^2))\)，應該差不多

代碼

轉載于:https://www.cnblogs.com/lstoi/p/9896784.html

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的【20181102T2】飞越行星带【智商题+最小瓶颈路】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。