题意：【模板】最小生成树
方法1：Prim算法(稠密边用优）
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,d,ans;
bool f[5001];
vector<pair<int,int>> a[5001];//用结构体和重载比直接定义小根堆似乎还快一点点
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;//直接定义小根堆优选队列
int main(){scanf("%d%d",&n,&m);while(m--){scanf("%d%d%d",&u,&v,&d);a[u].push_back({v,d});//双向存点和权值a[v].push_back({u,d});}f[1]=1;//1号节点赋初值，表示已访问//初始化将1号节点对应的边放入队列，权值放前便于优先队列按权值从小到大排序for(auto &v:a[1]) q.push({v.second,v.first});for(int i=1;i<n;i++){while(!q.empty()&&f[q.top().second]) q.pop();if(q.empty()){printf("orz");return 0;}v=q.top().second,d=q.top().first,q.pop();ans+=d,f[v]=1;//找到一个点，增加权值、标已访问for(auto &u:a[v]) q.push({u.second,u.first});//将当前个节点连通的点入队}printf("%d",ans);return 0;
}方法2：Kruskal算法(稀疏边用优）
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,d,cnt,ans,f[5001];
struct node{int x,y,dis;bool operator < (const node& i) const{return dis>i.dis;}
};
priority_queue<node> q;//未加参数，默认为大根堆优先队列
int myfind(int x){ return x==f[x]?x:f[x]=myfind(f[x]);
}
void Kruskal(){for(int i=1;i<=n;i++) f[i]=i;//初始化并查集while(!q.empty()&&cnt<n-1){int fx=myfind(q.top().x),fy=myfind(q.top().y),d=q.top().dis;q.pop();if(fx!=fy)f[fy]=fx,ans+=d,cnt++;}
}
int main(){scanf("%d%d",&n,&m);while(m--){scanf("%d%d%d",&u,&v,&d);q.push({u,v,d});//直接存边和权值，与prim算法区别}Kruskal();if(cnt==n-1) printf("%d",ans);else printf("orz");return 0;
}谢谢！