实现代码

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for std::pair
#include <cstring> // for memset
using namespace std;

const int MAXN = 5010, INF = 0x3f3f3f3f;

vector<pair<int, int>> g[MAXN]; // 改为邻接表存储图
int dist[MAXN], n, m, res;
bool book[MAXN];

void prim()
{
    memset(book, false, sizeof(book));
    for (int i = 1; i <= n; ++i) dist[i] = INF;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[1] = 0;
    pq.push(make_pair(0, 1));

    while (!pq.empty())
    {
        pair<int, int> top = pq.top();
        pq.pop();
        int d = top.first;
        int u = top.second;

        if (book[u]) continue;
        book[u] = true;
        res += d;

        for (size_t i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i].first;
            int w = g[u][i].second;
            if (!book[v] && w < dist[v])
            {
                dist[v] = w;
                pq.push(make_pair(w, v));
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, w);
    }

    res = 0;
    prim();
    bool all_connected = true;
    for (int i = 1; i <= n; ++i)
    {
        if (!book[i])
        {
            all_connected = false;
            break;
        }
    }
    if (!all_connected)
        cout << "orz";
    else
        cout << res;
    return 0;
}

通过这段代码我们来学习一下C++11以及C++STL

1 关于 vector<pair<int, int>> g[MAXN];

vector<pair<int, int>> g[MAXN]; 是一个数组，每个元素是一个向量（vector），这个向量存储了若干个 pair<int, int> 类型的数据。让我们详细解释这个声明：

逐层解析

1. pair<int, int>:

• pair<int, int> 是一个模板类，它存储一对值，这里的每个值都是 int 类型。比如，一个 pair<int, int> 可以表示一条边，其中第一个 int 是边连接的顶点，第二个 int 是该边的权重。

1. vector<pair<int, int>>:

• vector<pair<int, int>> 是一个向量，它的每个元素都是 pair<int, int> 类型。这个向量可以存储一个顶点的所有邻接边的信息。

1. vector<pair<int, int>> g[MAXN];:

• g[MAXN] 是一个长度为 MAXN（即 1000）的数组。数组的每个元素都是一个 vector<pair<int, int>>，即存储了一个顶点的所有邻接边。
• g[i] 表示图中第 i 个顶点的所有邻接边。g[i][j] 表示从顶点 i 出发的第 j 条边，这条边用一个 pair<int, int> 表示，pair 的第一个元素是该边的终点顶点，第二个元素是该边的权重。

示例

假设我们有一个简单的图，有 3 个顶点和 3 条边：

• 边 1: 顶点 1 到顶点 2，权重为 5
• 边 2: 顶点 1 到顶点 3，权重为 10
• 边 3: 顶点 2 到顶点 3，权重为 3

我们可以用以下代码填充 g 数组：

g[1].emplace_back(2, 5); // 顶点 1 到顶点 2，权重 5
g[1].emplace_back(3, 10); // 顶点 1 到顶点 3，权重 10
g[2].emplace_back(3, 3); // 顶点 2 到顶点 3，权重 3

g[2].emplace_back(1, 5); // 顶点 2 到顶点 1，权重 5 (无向图)
g[3].emplace_back(1, 10); // 顶点 3 到顶点 1，权重 10 (无向图)
g[3].emplace_back(2, 3); // 顶点 3 到顶点 2，权重 3 (无向图)

最终，g 数组将如下所示：

• g[1] 包含两条边：(2, 5) 和 (3, 10)
• g[2] 包含两条边：(1, 5) 和 (3, 3)
• g[3] 包含两条边：(1, 10) 和 (2, 3)

总结

vector<pair<int, int>> g[MAXN]; 用于表示图的邻接表，其中 g[i] 是一个向量，存储了从顶点 i 出发的所有边的终点和权重信息。这种表示方法在处理稀疏图（即边数远少于顶点数的图）时非常高效。

2 关于 emplace_back

emplace_back 是 C++11 引入的一个 STL 容器方法，用于在容器（如 vector、list 等）的末尾直接构造元素。与 push_back 相比，emplace_back 更高效，因为它可以直接在目标位置构造对象，而不需要先构造临时对象再复制或移动到容器中。

emplace_back 的使用示例

#include <vector>
#include <utility>
#include <iostream>

int main() {
    std::vector<std::pair<int, int>> vec;

    // 使用 push_back 插入元素
    vec.push_back(std::make_pair(1, 2));

    // 使用 emplace_back 插入元素
    vec.emplace_back(3, 4);

    // 输出向量内容
    for (const auto& p : vec) {
        std::cout << "(" << p.first << ", " << p.second << ")\n";
    }

    return 0;
}

在上述代码中：

• vec.push_back(std::make_pair(1, 2)); 首先用 std::make_pair 构造一个 pair<int, int> 对象，然后将其复制或移动到 vec 的末尾。
• vec.emplace_back(3, 4); 直接在 vec 的末尾构造一个 pair<int, int> 对象。

主要区别

• push_back：需要先构造临时对象，再将该对象复制或移动到容器中，涉及一次复制或移动操作。
• emplace_back：直接在容器末尾构造对象，不需要额外的复制或移动操作。

效率比较

emplace_back 通常比 push_back 更高效，尤其是在对象构造比较复杂或对象不支持移动语义的情况下，因为它省去了临时对象的创建和复制/移动的过程。

具体到你的代码

g[a].emplace_back(b, w);
g[b].emplace_back(a, w);

这里 g[a].emplace_back(b, w); 和 g[b].emplace_back(a, w); 的作用是直接在 g[a] 和 g[b] 的末尾构造一个 pair<int, int>，对应的边分别是 (b, w) 和 (a, w)。这样可以高效地将边信息添加到邻接表中。

3 关于 priority_queue的定义

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

这行代码定义了一个名为 pq 的优先队列。优先队列是一种特殊的队列结构，能够以高效的方式访问并移除具有最高优先级的元素。让我们详细解释这个定义：

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

逐部分解释

1. priority_queue<...>:

• 这是优先队列的模板类，定义了一个优先队列。

1. pair<int, int>:

• 优先队列中存储的元素类型是 pair<int, int>。每个元素是一个整数对。

1. vector<pair<int, int>>:

• 这是底层容器类型，指定优先队列内部使用 vector 作为存储数据的容器。优先队列通常使用堆（heap）结构实现，而 vector 是一个动态数组，非常适合堆的实现。

1. greater<pair<int, int>>:

• 这是一个比较函数对象，定义了优先队列的排序方式。默认情况下，priority_queue 是一个最大堆，意味着最大元素具有最高优先级。如果你想要一个最小堆（即最小元素具有最高优先级），可以使用 greater<...> 进行比较。这里的 greater<pair<int, int>> 表示优先队列按照 pair<int, int> 中的第一个元素进行升序排序。

综上所述

这行代码定义了一个优先队列 pq，它的元素是 pair<int, int> 类型。优先队列内部使用 vector 作为底层容器，并且按照 pair<int, int> 的第一个元素进行升序排序，即最小堆。

应用场景

在我的代码中，这个优先队列用于 Prim 算法。pair<int, int> 中，第一个 int 表示边的权重（优先级），第二个 int 表示顶点编号。通过使用 greater<pair<int, int>>，优先队列总是将权重最小的边放在顶部，从而方便 Prim 算法每次选择最小权重的边扩展生成树。

示例

假设你往 pq 中插入以下元素：

pq.push(make_pair(10, 1));
pq.push(make_pair(5, 2));
pq.push(make_pair(20, 3));
pq.push(make_pair(1, 4));

此时，优先队列的顺序是：

1. (1, 4)
2. (5, 2)
3. (10, 1)
4. (20, 3)

每次调用 pq.top() 时，将返回权重最小的元素 (1, 4)，从而帮助 Prim 算法选择当前最小的边进行扩展。