题解 | #道路建设#

题解（最小生成树）

kruskal

博客链接：
https://blog.csdn.net/qq_50285142/article/details/116995428

#include<bits/stdc++.h>
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

#include<bits/stdc++.h>
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;
}