鏈接：https://ac.nowcoder.com/acm/contest/27302/L
來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld
題目描述
谷寶最近完成了ImmersiveEngineering（IE）的各種重型機械和發電機的建設，但是基地上空密密麻麻的電線讓他覺得非常不美觀。他決定用工程師剪線鉗把所有電線全部拆除之后重新用高壓電線設置電網。

每一個重型機械或發電機都有且只有一個接線器用來連接電線，谷寶的目標只有一個，那就是讓整個基地的所有接線器連在同一個電網中所需求的電線總長度最短。由于電線在制作時只能制作整數長度，所以對于兩接線器之間距離不為整數的，其需求的電線長度需要向上取整。

形式上，若兩接線器A、B的坐標分別為(X_A,Y_A,Z_A),(X_B,Y_B,Z_B)(X
A
?
,Y
A
?
,Z
A
?
),(X
B
?
,Y
B
?
,Z
B
?
)，則他們之間的距離為\lceil \sqrt{(X_A-X_B)^2+(Y_A-Y_B)2+(Z_A-Z_B)^2}\rceil?
(X
A
?
?X
B
?
)
2
+(Y
A
?
?Y
B
?
)
2
+(Z
A
?
?Z
B
?
)
2

?
?，其中\lceil \rceil??為向上取整，即不小于當前數字的最小整數。例如\lceil 3\rceil = 3?3?=3,\lceil 3.14\rceil=4?3.14?=4。

輸入描述:
第一行包含一個正整數n(n\leq2000)n(n≤2000)，表示接線器的數量。

接下來nn行，每行包含三個整數xx、yy和zz（|x|,|y|,|z|\leq10^9∣x∣,∣y∣,∣z∣≤10
9
）表示接線器的空間坐標。

輸出描述:
需求的電線的最短總長度。
示例1
輸入
復制
5
0 0 0
1 0 0
-1 0 0
0 1 0
0 -1 0
輸出
復制
4
備注:
c++的cmath頭文件中的ceil函數可以實現浮點數的向上取整，例如：ceil(x)返回x向上取整的結果。

思路 ：

• 完全圖的最小生成樹，數據保證$O(n^2)$能過
• 這里用prim解最小生成樹問題
• 如果用kruskai從邊入手，要把這個完全圖中所有邊都存一遍，且每條邊還要存點的信息，是很麻煩的；如果用prim從點入手，每次考慮點即可，要存的信息也只有點的坐標，以及當前點的距離（使用函數，不需要預處理所有邊）

#include <iostream> #include <cstring> #include <vector> #include <math.h> using namespace std;typedef long long ll; const int N = 2010;int n; bool st[N]; ll dist[N]; struct Point {ll x, y, z; }; Point p[N];ll get_dist(int a, int b) {return ceil(sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y) + (p[a].z - p[b].z) * (p[a].z - p[b].z))); }int main() {cin >> n;for (int i = 0; i < n && cin >> p[i].x >> p[i].y >> p[i].z; i ++ );memset(dist, 0x3f, sizeof dist);dist[0] = 0;ll res = 0;for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 0; j < n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;res += dist[t];for (int j = 0; j < n; j ++ )dist[j] = min(dist[j], get_dist(t, j));}cout << res << endl; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的WireConnection 最小生成树，prim 第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛的全部內容，希望文章能夠幫你解決所遇到的問題。

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