Who's Studio.

hihoCoder#1109 - 最小生成树三·堆优化的Prim算法

Word count: 425Reading time: 2 min
2016/05/17

题目

给定一个无向图，求最小生成树。
具体描述请见hihoCoder。

解题思路

这是采用堆实现的Prim算法（与Dijkstra算法十分相似）。这里是Prim算法朴素的实现。

时间复杂度

时间复杂度为MlogN。

代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

struct HeapNode {
	int id = -1;
	int d = -1;
	HeapNode(int i, int di) {
		id = i;
		d = di;
	}
};

struct Node {
	int id = -1;
	int d = -1;
	vector<int> neighbors;
	vector<int> edges;
};

struct NodeCmp {
	bool operator()(const HeapNode& a, const HeapNode& b) const {
		return a.d > b.d;
	}
};

int prim(Node* graph, int N) {
	bitset<100001> set;
	set.reset();
	priority_queue<HeapNode, vector<HeapNode>, NodeCmp> heap;
	graph[1].d = 0;
	set[1] = 1;
	for (int i = 0; i < graph[1].neighbors.size(); i++) {
		graph[graph[1].neighbors[i]].d = graph[1].edges[i];
		heap.push(HeapNode(graph[1].neighbors[i], graph[graph[1].neighbors[i]].d));
	}

	int minCost = 0;
	int i = 0;
	while (i < N - 1) {
		HeapNode shortestNode = heap.top();
		heap.pop();
		if (set[shortestNode.id])
			continue;
		i++;
		set[shortestNode.id] = 1;
		minCost += shortestNode.d;
		for (int j = 0; j < graph[shortestNode.id].neighbors.size(); j++) {
			if (set[graph[shortestNode.id].neighbors[j]])
				continue;
			if (graph[graph[shortestNode.id].neighbors[j]].d == -1 || graph[shortestNode.id].edges[j] < graph[graph[shortestNode.id].neighbors[j]].d)
				graph[graph[shortestNode.id].neighbors[j]].d = graph[shortestNode.id].edges[j];
			heap.push(HeapNode(graph[graph[shortestNode.id].neighbors[j]].id, graph[graph[shortestNode.id].neighbors[j]].d));
		}
	}

	return minCost;
}

int main() {
	int N = 0, M = 0;
	cin >> N >> M;
	Node* graph = new Node[N + 1];
	for (int i = 1; i < N + 1; i++)
		graph[i].id = i;
	for (int i = 1; i < M + 1; i++) {
		int a = 0, b = 0, edge = 0;
		cin >> a >> b >> edge;
		graph[a].neighbors.push_back(b);
		graph[a].edges.push_back(edge);
		graph[b].neighbors.push_back(a);
		graph[b].edges.push_back(edge);
	}

	cout << prim(graph, N) << endl;

	delete[] graph;

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/17/2016-05-17-hihocoder-prim-by-heap/

Publish date：May 17th 2016, 12:41:05 pm

Update date：December 4th 2022, 5:11:06 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目