53. 寻宝（第七期模拟笔试） (kamacoder.com)
1.prim算法
#include<bits/stdc++.h>
using namespace std;
int main(){int e,v;int x,y,k;cin>>v>>e;vector<vector<int>>grid(v+1,vector<int>(e+1,10001));while(e--){cin>>x>>y>>k;grid[x][y]=k;grid[y][x]=k;}vector<int>minDist(v+1,10001);vector<bool>isIntree(v+1,false);for(int i=1;i<v;i++){int cur=-1;int minval=INT_MAX;for(int j=1;j<=v;j++){if(!isIntree[j]&&minDist[j]<minval){minval=minDist[j];cur=j;}}isIntree[cur]=true;for(int j=1;j<=v;j++){if(!isIntree[j]&&grid[cur][j]<minDist[j]){minDist[j]=grid[cur][j];}}}int result=0;for(int i=2;i<=v;i++){result+=minDist[i];}cout<<result<<endl;
}2.kruskal算法
#include<bits/stdc++.h>
using namespace std;
struct Edge{int l,r,val;
};
int n=10001;
vector<int>father(n,-1);
void init(){for(int i=0;i<n;i++){father[i]=i;}
}
int find(int u){return u==father[u]?u:father[u]=find(father[u]);
}
void join(int u,int v){u=find(u);v=find(v);if(u==v){return;}father[v]=u;
}
bool isSame(int u,int v){u=find(u);v=find(v);return u==v;
}
int main(){int v,e;int v1,v2,val;vector<Edge>edges;int result_val=0;cin>>v>>e;while(e--){cin>>v1>>v2>>val;edges.push_back({v1,v2,val});}sort(edges.begin(),edges.end(),[](const Edge& a,const Edge& b){return a.val<b.val; });init();for(Edge edge:edges){int x=find(edge.l);int y=find(edge.r);if(x!=y){result_val+=edge.val;join(x,y);}}cout<<result_val<<endl;return 0;
}
总结
最小生成树模板题，使用prim算法和kruskal算法。弄清楚原理后背模板。prim算法适用于稠密图，时间复杂度是O(n^2),kruskal算法适用于稀疏图,时间复杂度是O(nlogn)。都是采用贪心策略
