1645 . 電路啟動方案
TopCoder
Tags
Description
給定一個大小為 N x M 平版上 F 個點的座標，請求出一顆生成樹 T 使得其總花費最小。
連接兩點 Pi, Pj 的花費為 |Xi-Xj| + |Yi-Yj| 。
/*
普蘭納市是斯凱利國的首都，位於斯凱利國正中央的位置。普蘭納這個都市具有凌駕於全世界之上的科技發展程度，
他們具有能夠將許許多多的科技硬體產物都壓成平板狀的「普蘭納技術」，這種超群的技術除了能夠因此省下很多空間外，竟還能增強其物件本身運作效能！
其中，有普蘭納市中央發電廠之稱的便是「普蘭納發電廠」，其負責了普蘭納市將近 71.4285% 的電力供給，其重要性不言自明。
而這座發電廠當然也使用了普蘭納都市特有的「普蘭納技術」來加強其運作進程，包括將製造出來的電力能源以「普蘭納化」後的電路裝置傳輸，
每個「普蘭納化」後的電力傳輸裝置都可以視為一個完美的平版，上面布著 N×M 個等大的正方型網格(grids)，並定最左上角的網格座標為(0, 0)、
最右下角的網格座標為(N-1, M-1)。每一個網格上有可能有著一些「電力傳輸元件」，而他們之間必須以被「電磁化」的網格
（包含那些上面有「電力傳輸元件」的網格和空格）來連結這些「電力傳輸元件」，使得任意二個「電力傳輸元件」都能利用互相相鄰
（即兩的網格之間有條共用的邊）的被「電磁化」的網格所形成的「電磁通道」連接（即可以藉由被「電磁化」的網格互相到達）。
這麼一來不但可以縮減裝置所佔用的空間，更能減少輸送過程中的電力耗損。
在平時，普蘭納發電廠中的電路傳輸工作都是交由普蘭納電腦去對每個電力傳輸裝置分配好最佳方案。
但現在很不幸的，在發電廠 ARD-14 區域，有一個很重要的電力傳輸裝置它的專屬配置系統壞掉了！因此，現在需要強大的你來幫忙手動操作，
你的工作就是原本配置系統要做的事──決定哪些空格該被「電磁化」，使得該電力傳輸裝置可以正常的被運作（符合運作條件）。
然而，因為每建立一條「電磁通道」都需付出一定的代價，其代價便是該條「電磁通道」所經過的網格數 - 1。因此你當然想要使得須付出的代價總和越小越好。
*/
Input Format
本題輸入的測試檔只有單筆測試資料，第一行有三個整數 N、M、F，
接下來有 F 行，其中的第 i 行會給出第 i 個點的座標 (Xi, Yi)。
對於所有測試資料，保證1 ≤ N, M ≤ 1000000007，0 ≤ F ≤ 200000，0 ≤ Xi < N, 0 ≤ Yi < M。
座標保證皆為整數。
/*
本題輸入的測試檔只有單筆測試資料，第一行有三個整數 N、M、F，
F 代表現在要處理的電力傳輸裝置上有幾個「電力傳輸元件」。
接下來有F行，其中的第 i行會給出第i個「電力傳輸元件」在電力傳輸裝置上的網格座標 (Xi, Yi)。
對於所有測試資料，保證1 ≤ N, M ≤ 1000000007，0 ≤ F ≤ 200000，0 ≤ Xi < N, 0 ≤ Yi < M。
*/
Output Format
請輸出一個整數 S 代表最小花費。
/*
一個整數S代表至少要付出多少代價才能使輸入的電力傳輸裝置正常運作。
*/
Sample Input 1
5 5 4
0 2
2 0
2 4
4 2
0 2
2 0
2 4
4 2
Sample Output 1
12
Hints
Problem Source
原TIOJ1645 / Skyly & Shik Contest II (Problem F)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |