道路建设（牛客竞赛）（最小生成树prim+kruskal）（详细讲解）

题目链接

道路建设

题解（最小生成树）

kruskal

需要掌握的知识(前备知识)：

1.并查集的使用

2.图的边的存储（结构体存储）（还有其他的存储方式，本题以结构体存储为例）

kruskal算法步骤：

1.首先做好所有的初始化工作：

• 并查集初始化（很容易忘的）
• 结构体存边

2.对所有边按权值从小到大进行排序，因为是最小生成树嘛，肯定是从小的权值往大的权值挑选边的。

3.对每条边进行遍历，记录当前访问的边的两个的点，查找这两个点的父亲节点，如果两个父亲节点一样，说明他们在一个集合里面，他们之前已经连通了，此时如果再连，就会形成回路，所以要跳过去，进行下一层循环

4.对父亲节点不一样的点，把他们的父亲节点设为一样的，为加入到最小生成树的操作，同时更新最小生成树的权值

#include
using namespace std;
typedef long long ll;
const int N = 1e2+10;
struct edge
{int u,v,w;
}e[N*N];
ll n,m,c,f[N];
ll find(ll x){return x==f[x] ? x :(f[x]=find(f[x]));}//路径压缩
bool cmp(edge a,edge b)
{return a.w<b.w;
}
void kruskal()
{ll ans = 0,cnt=0;for(int i=1;i<=n;i++) f[i]=i;//注意初始化sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){//查找父亲节点int a = find(e[i].u);int b = find(e[i].v);if(a==b)continue;//父亲节点一样，会形成回路，去掉这种情况f[b] = a;++cnt;ans += e[i].w;}if(ans > c) cout<<"No\n";else cout<<"Yes\n";
}
int main()
{while(cin>>c>>m>>n){for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;kruskal();}return 0;
}

prim

这个有很多注意点的：

我就是g[][]数组没有初始化找了很长时间的错误，而且vis数组，dis数组都要初始化

我想口述一下对这个算法的理解：

prim算法就是对每个节点进行遍历，最小生成树一定包括所有的节点

把最小生成树当做一个点的集合

从一个节点开始遍历，找距离这个集合最近的点（对集合中所有的点来说），刚开始这个集合为空，所有点到这个集合距离都初始化为inf；

到遍历第二个点时因为第一个点加入了最小生成树，如果这两个点存在路径,t = j，ans就会加上这个路径的权值。

每次对点的循环进行的过程就是：
找距离最小生成树点集合最小的点，标记该点，更新所有点到新加入最小生成树集合的点的距离

#include
using namespace std;
typedef long long ll;
const int N = 105;
const int inf = 0x3f3f3f3f;
int g[N][N];
int dis[N],res;
ll c,n,m;
bool vis[N];
void prim()
{res = 0;for(int i=1;i<=n;i++) g[i][i] = 0;for(int i=1;i<=n;i++) dis[i] = inf,vis[i] = false;for(int i=0;i<n;i++){int t = -1;//找距离最小生成树集合的距离最近的点for(int j=1;j<=n;j++){if(!vis[j] && (t==-1 || dis[t] > dis[j])) t = j;}if(i && dis[t]==inf){res = inf;return;}if(i) res += dis[t];vis[t] = true;//将该点加到最小生成树的集合for(int j=1;j<=n;j++) dis[j] = min(dis[j],g[t][j]);//因为前面加了一个t节点，是新加入的节点，所以需要更新所有点到这个点的最短距离，因为之前没有这样的值更新}
}
int main()
{while(cin>>c>>m>>n){memset(g,inf,sizeof(g));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u][v] = g[v][u] = min(w,g[u][v]);}prim();if(res > c) cout<<"No\n";else cout<<"Yes\n";}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！