53.寻宝

采用两种最小生成树算法分别来做一下

Prim算法

  #include <iostream>#include<vector>
#include<climits>using namespace std;#define endl '\n'int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int v,e;int x,y,k;cin>>v>>e;vector<vector<int>>grid(v+1,vector<int>(v+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,0);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]=1;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;return 0;}

kruskal算法

  #include <iostream>#include<vector>
#include<algorithm>using namespace std;#define endl '\n'int n=10001;
vector<int>father(n,-1);
struct Edge
{int l,r,val;
};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;
}int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int v,e;int v1,v2,v3;vector<Edge>edges;int result_val=0;cin>>v>>e;while(e--){cin>>v1>>v2>>v3;edges.push_back({v1,v2,v3});}sort(edges.begin(),edges.end(),[](const Edge&a,const Edge&b){return a.val<b.val;});vector<Edge> result;init();for(Edge edge:edges){int x=find(edge.l);int y=find(edge.r);if(x!=y){result.push_back(edge);result_val+=edge.val;join(x,y);}}cout<<result_val;return 0;}