题目描述：
$n$ 个平面上的点，求出连接所有点的最小总花费。
数据范围：
$1\le n \le 1000; -10^6 \le x,y \le 10^6$
题解：
最小生成树，但是没有给出图。是个稠密图，稠密图中prim算法效果会比kruskal好。
prim算法可以直接使用 dijkstra模板，可以在访问出边的时候加上一个判断，优化时间复杂度。注意从优先级队列中取出一个元素之后需要将距离修改为 $0$ ，或者在访问出边时不加 $dis[u]$ ，因为看的是边的权重。
代码：
kruskal：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution
{
public:
struct Edge
{
int u, v, w;
bool operator<(const Edge &p) const { return this->w < p.w; }
};
struct UF
{
vector<int> fa;
UF(int n) : fa(n)
{
for (int i = 0; i < n; ++i)
fa[i] = i;
};
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
void unite(int u, int v)
{
int up = find(u), vp = find(v);
if (up != vp)
fa[up] = vp;
}
bool isConnect(int u, int v) { return find(u) == find(v); }
};
int getManDis(vector<int> &px, vector<int> &py)
{
return abs(px[0] - py[0]) + abs(px[1] - py[1]);
}
int minCostConnectPoints(vector<vector<int>> &points)
{
int n = points.size();
UF uf(n);
vector<Edge> edges;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
edges.push_back({i, j, getManDis(points[i], points[j])});
sort(edges.begin(), edges.end());
int ans = 0;
for (auto &edge : edges)
{
if (!uf.isConnect(edge.u, edge.v))
{
ans += edge.w;
uf.unite(edge.u, edge.v);
}
}
return ans;
}
};
|
prim：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
int getManDis(vector<int> &px, vector<int> &py)
{
return abs(px[0] - py[0]) + abs(px[1] - py[1]);
}
int minCostConnectPoints(vector<vector<int>> &points)
{
int n = points.size();
vector<bool> vis(n, false);
vector<int> dis(n, INF);
priority_queue<pair<int, int>> q;
q.push({0, 0});
dis[0] = 0;
int ans = 0;
while (q.size())
{
auto out = q.top();
q.pop();
if (vis[out.second])
continue;
vis[out.second] = true;
ans += out.first;
for (int i = 0; i < n; ++i)
{
if (i == out.second || vis[i])
continue;
int w = getManDis(points[out.second], points[i]);
if (w < dis[i])
{
dis[i] = w;
q.push({-w, i});
}
}
}
return ans;
}
};
|