製作在圖中的成本矩陣

問題：

形成一個網絡，即，所有的基礎應當從每個基地可達。如果存在隧道連接基地的路徑，則可以從其他基地到達一個基地。基礎是基於具有整數座標的二維平面。（x1，y1）和（x2，y2）分別爲min {| x1-x2 |，| y1-y2 | }。製作在圖中的成本矩陣

網絡形成的最低成本是多少？

1 ≤ N ≤ 100000 // Number of bases 
-10^9 ≤ xi,yi ≤ 10^9

典型Kruskal的最小生成樹 implementation.But - 可以不存儲（10^5）^ 2層的邊緣。那麼，我應該如何讓我的成本矩陣，如何使圖形，所以我可以應用克魯斯卡爾算法？

來源

2014-12-19 QWE

你確定它是'min {...}'而不是'max {...}'嗎？因爲如果它是'min'，那會造成一個非常奇怪的答案。 – user3386109 2014-12-19 09:46:36

@ user3386109你是最小 – QWE 2014-12-19 09:48:04

您不應該存儲整個圖形，因爲您並不需要它。實際上在這種情況下，我認爲Prim's算法更適合這種情況。在任何時候您都不需要所有的邊，而是在每次迭代中，您將更新大小爲N的最小分佈數組。當然，複雜性仍然是按照N**2的順序，但至少內存不會成爲問題。您還可以進一步使用特定的距離計算方法來提高複雜度（使用一些有序結構來存儲點）。

來源

2014-12-19 09:58:35

我相信將會使用的唯一邊緣（由於您的成本函數）將從每個基地到最多4個鄰居。使用的鄰居是x值最大（或相等）的最近點，x值較小（或相等）的最近點，y值較大（或相等）的最近點，較小（或相等） y值。

您可以通過按照每個軸對各點進行排序，然後按照排序順序將每個點與其前後的點進行鏈接來高效計算這些鄰居。

如果在座標的特定值處有多個點，則無關緊要。

因此，只有O（4n）邊需要考慮使用Kruskal算法。

來源

2014-12-19 10:25:06

我已經通過排序x和y來實現這個[這裏有一個樣子]（http://ideone.com/QZi8U3），但它給了我一個超時的時間限制錯誤 – QWE 2014-12-19 11:21:14

製作在圖中的成本矩陣

回答

相關問題