prim算法精讲
普利姆算法用于求最小生成树
三步：
1.选择离树最近的点
2.该点加入树
3.更新距离表
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){
int v,e;
cin>>v>>e;
vector<vector<int>>grid(v+1,vector<int>(v+1,10001));
for(int i=0;i<e;i++){
int v1,v2,val;
cin>>v1>>v2>>val;
grid[v1][v2]=val;
grid[v2][v1]=val;
}
vector<int>minDist(v+1,10001);
vector<bool>isInTree(v+1,false);
for(int j=1;j<v;j++){
//第一步选取距离最小的点
int min=INT_MAX;
int cur;
for(int i=1;i<=v;i++){
if(!isInTree[i]&&minDist[i]<min){
min=minDist[i];
cur=i;
}
}
//当前节点加入集合
isInTree[cur]=true;
//更新当前minDist
for(int i=1;i<=v;i++){
if(!isInTree[i]&&grid[cur][i]<minDist[i]){
minDist[i]=grid[cur][i];
}
}
}
int ans=0;
for(int i=2;i<=v;i++){
ans+=minDist[i];
}
cout<<ans;
}注意！！！vector<vector<int>>grid(v+1,vector<int>(v+1,10001));
这一行很重要
不能初始化为0 这样不存在的边的权值为0 ，应该把不存在的边的权值设为最大值！！！！！！！
kruskal算法精讲
lambda表达式：
一句话：
“一次性、匿名、可调用对象”，本质上编译器帮你生成一个未命名的函数对象类（closure type）。
“方括号抓变量，圆括号写参数，箭头指返回，花括号干正事。”
[ capture ] ( parameter_list ) { body }
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n=10000;
struct edge{
int v1,v2,val;
edge(int _v1,int _v2,int _val):v1(_v1),v2(_v2),val(_val){}
};
vector<int>father(n+1,0);
void init(){
for(int i=0;i<father.size();i++){
father[i]=i;
}
};
int find(int x){
if(father[x]==x)return x;
else return father[x]=find(father[x]);
}
bool isSame(int x,int y){
x=find(x);
y=find(y);
return x==y;
}
void join(int u, int v){
u=find(u);
v=find(v);
if(u==v) return ;
father[v]=u;
}
int main(){
//数据读取
int v,e;
cin>>v>>e;
vector<edge>edges;
for(int i=0;i<e;i++){
int v1,v2,val;
cin>>v1>>v2>>val;
edges.push_back(edge(v1,v2,val));
}
//排序
sort(edges.begin(),edges.end(),[](edge &a,edge &b){
return a.val<b.val;
});
int ans=0;
init();
//贪心选择
for(auto _e:edges){
int l=_e.v1;
int r=_e.v2;
int val=_e.val;
if(isSame(l,r)){ //不是同一个集合的
continue;
}else{
join(l,r);
ans+=val;
}
}
cout<<ans;
}