一、题目：
二、题解：
2.1：在朴素算法中，prim的核心代码太过冗余(也就是遍历寻找最小边)
- 此为朴素算法代码
dis[1] = 0; // 从节点1开始，初始权重为0int res = 0; // 记录最小生成树的总权重for (int i = 1; i <= n; i++) // 进行n次选择最小值操作{ int temp = -1; // 用于记录当前最小值对应的节点// 遍历所有节点，找出距离最小的未加入最小生成树的节点for (int j = 1; j <= n; j++) { //和Dijkstra一样,//1.当j这个点还没访问过，2.遍历的的点j<当前点temp的距离,那么就更新temp//temp==-1只是为了确保其能够第一次进入循环，详解看Dijkstraif (!st[j] && ((temp == -1) || (dis[j] < dis[temp]))) {temp = j;}}//此时temp就是距离intree最近的点if (temp == -1) // 如果所有节点都已经被选中，说明图不连通,直接return{ cout << -1 << '\n';return; }
2.2、我们只是想依次取出距离最小的点，因此想到可以使用优先队列优化.
0）假设我们现在有这样一幅图
1）首先我们把[1]这个点放入优先队列里面，while[pq.size()]中挨个top+pop,此时[1]这个点就是距离intree[]最近的点
2）枚举[1]的所有出边，来更新dis[i]
- 更新之后，图变成了:
3）此时，我们把[1]和[4]存入intree[]当中
4）由于priority_queue()的特性，我们会取出[{2,1}]，即此时[2]为距离原点最近的点，并且枚举[2]的所有出边，来更新dis[i]…
- 重复2)、3)操作
5）总结：
三、代码解析：
3.1代码分块
这份代码是实现了 Prim 算法，通过优先队列（小根堆）来优化求解最小生成树（MST）。我们可以将它分成几个部分来逐步解析：
1. 节点结构体定义和优先队列的自定义比较规则
struct node{int v; //点int w; //权重bool operator < (const node& u)const //重写<，构建小根堆{return w == u.w ? v < u.v : w > u.w;}
};
-
node结构体用于表示图中的边。每个节点包含两个信息：v：表示节点编号。w：表示边的权重。
-
operator <：这是重载小于运算符，用来指定优先队列的排序规则：- 如果两个节点的权重相同，按照节点编号
v的大小进行排序。 - 否则，按照权重
w大小进行降序排序（这里为了实现小根堆，较小的权重在堆顶）。
- 如果两个节点的权重相同，按照节点编号
2. 变量声明
vector<node>g[N]; // 存储图的邻接表
int dis[N]; // 存储从源节点到每个节点的最短距离
bool st[N]; // 状态数组，记录节点是否已加入最小生成树
int n,m; // n为节点数，m为边数
g[N]：邻接表，用来存储图的边。每个节点有一个vector<node>来存储与它相连的其他节点和对应的边权重。dis[N]：最短距离数组，dis[i]记录从源节点到节点i的最短距离。st[N]：状态数组，用来标记某个节点是否已经被加入最小生成树（MST）。n和m：分别表示节点数和边数。
3. solve 函数：核心算法实现
void solve()
{memset(dis,0x3f,sizeof(dis)); // 初始化所有距离为最大值cin >> n >> m;for(int i = 1; i <= m; i++) {int ui, vi, wi;cin >> ui >> vi >> wi; g[ui].push_back({vi, wi}); // ui->vi，权重为wig[vi].push_back({ui, wi}); // 对无向边的处理}
memset(dis, 0x3f, sizeof(dis));：初始化dis数组的所有值为一个很大的数（0x3f表示的值是 63 或 63的高位），这是为了模拟无穷大，表示初始时从源节点到其他节点的距离都是未知的。- 接着输入
n和m，表示节点数和边数。 - 通过
for循环读取每一条边，存入邻接表g中，注意无向图需要将每条边都存两次（g[ui].push_back({vi, wi})和g[vi].push_back({ui, wi})）。
4. 初始化和优先队列操作
int res = 0;dis[1] = 0; // 从节点 1 开始，起点到自己的距离为 0st[1] = true; // 标记节点 1 已经加入 MSTpriority_queue<node> pq;pq.push({1, 0}); // 将起点 1 入堆，权重为 0
dis[1] = 0：设定起始节点（这里选择节点 1）的距离为 0。st[1] = true：标记起点已经被加入 MST。priority_queue<node> pq：创建一个优先队列（小根堆），用于每次选择当前最小权重的节点。pq.push({1, 0})：将起点节点 1 和它的距离（0）加入优先队列。
5. 主循环：构建最小生成树
while(pq.size()) { // 堆非空，继续进行auto t = pq.top().v; pq.pop(); // 取出堆顶节点st[t] = true; // 标记当前节点已经加入 MSTres += dis[t]; // 累加当前节点的最小距离到结果dis[t] = 0; // 将该节点的距离置为 0for(auto &x : g[t]) { // 遍历所有与 t 相连的节点int y = x.v; // 目标节点int w = x.w; // 边的权重if(!st[y] && (dis[t] + w) < dis[y]) { // 如果目标节点还没加入 MST 且新的距离更小dis[y] = dis[t] + w; // 更新最短距离pq.push({y, dis[y]}); // 将更新后的节点加入堆}}}
while(pq.size())：当优先队列不为空时，继续处理。auto t = pq.top().v; pq.pop();：取出并弹出堆顶元素（当前距离最小的节点）。st[t] = true;：标记节点t已加入 MST。res += dis[t];：将当前节点的最短距离累加到结果res中。dis[t] = 0;：将该节点的距离置为 0，表示已经处理过。for(auto &x : g[t])：遍历当前节点t所有相邻的边，更新相邻节点的距离。
6. 检查最小生成树是否构建完整
for(int i = 1; i <= n; i++) if(st[i] == false) res = -1; // 如果有节点没有被访问过，说明无法构建 MSTcout << res << '\n';
}
for循环检查是否所有节点都已经被加入到 MST。如果有节点没有被访问到，则返回-1表示无法构成最小生成树（即图不连通）。- 如果所有节点都在 MST 中，则输出结果
res。
3.2：完整代码解析：
#include<bits/stdc++.h>
using namespace std;const int N=2e5+7;
struct node{int v; //点int w; //权重bool operator < (const node& u)const //重写<，构建小根堆{return w == u.w ? v < u.v : w > u.w;}
};
vector<node>g[N];
int dis[N]; //距离数组
bool st[N]; //状态数组intree
int n,m;void solve()
{memset(dis,0x3f,sizeof(dis));//初始化cin>>n>>m;for(int i=1;i<=m;i++){int ui,vi,wi;cin>>ui>>vi>>wi; g[ui].push_back({vi,wi}); //ui->vi，权重为wig[vi].push_back({ui,wi}); //对无向边的处理}int res=0;dis[1]=0; //从1开始，1的权重为0st[1]=true;priority_queue<node>pq;pq.push({1,0}); //从1开始，权重为0while(pq.size()) //堆非空{auto t=pq.top().v;pq.pop(); //取出+弹出堆顶//选择t这个点 st[t]=true;res+=dis[t]; //累计t的权重dis[t]=0; //把t距离清0for(auto &x:g[t]) //取出t所有指向的边{int y=x.v; //取出x的指向点+指向边的权重int w=x.w;//目标点没有被访问过//当前点的权重+w<目标点的权重if(!st[y] && (dis[t]+w)<dis[y]){dis[y]=dis[t]+w;pq.push({y,dis[y]});}}}//不存在最小生成树for(int i=1;i<=n;i++) if(st[i]==false) res=-1; cout<<res<<'\n';
} int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;while(_--) solve();return 0;
}