题解 | #道路建设#

//最小生成树模板题，用普利姆算法或克鲁斯卡尔算法求解。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = (10000+10)*2;
const int maxnn = 100+10;
struct sy{
    int next;
    int to;
    int w;
} edge[maxn];
int head[maxnn];
int cnt = 0;
struct Node{
    int number;
    int len;
    bool operator < (const Node& n) const
    {
        return n.len<len;
    }
} node[maxnn];
int c, n, m;
priority_queue<Node> pq;
int ans = 0;
bool vis[maxn];
void add_edge(int u, int v, int w)
{
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
}
void init()
{
    ans = 0;
    memset(vis, 0, sizeof vis);
    memset(edge, 0, sizeof edge);
    memset(head, 0, sizeof head);
    cnt = 0;
}
bool prim()
{
    pq.push({1, 0});
    while (pq.size())
    {
        int number = pq.top().number;
        int len = pq.top().len;
        pq.pop();
//         cout<<"number="<<number<<endl;
        if (vis[number]) continue;
//         cout<<"len="<<len<<endl;
        ans += len;
        vis[number] = true;
        for (int i=head[number];i;i = edge[i].next)
        {
            int next = edge[i].to;
            int w = edge[i].w;
            if (vis[next]) continue;
            pq.push({next, w});
        }
    }
    for (int i=1;i<=m;i++)
    {
//         cout<<"vis[i]="<<vis[i]<<endl;
        if (!vis[i]) return false;
    }
    return true;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int v1, v2, h;
    while (cin>>c>>n>>m)
    {
        init();
        for (int i=1;i<=n;i++)
        {
            cin>>v1>>v2>>h;
            add_edge(v1, v2, h);
            add_edge(v2, v1, h);
        }
        //普利姆算法求最小生成树。
        bool flag = prim();
//         cout<<"flag="<<flag<<endl;
//         cout<<"ans="<<ans;
        if (ans<=c&&flag) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}
//克鲁斯卡尔的做法，一定要记得排序
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = (10000+10)*2;
const int maxnn = 100+10;
int cnt = 0;
int ans = 0;
int num = 0;
int c, n, m;
struct sy{
    int u;
    int v;
    int w;
} edge[maxn];
int fa[maxnn];
int vis[maxnn][maxnn];
pair<int, int> a[maxn];

bool cmp(sy a1, sy a2)
{
    return a1.w<a2.w;
}

void init()
{
    num = 0;
    cnt = 0;
    ans = 0;
    memset(vis, 0, sizeof vis);
    for (int i=0;i<maxnn;i++)
    {
        fa[i] = i;
    }
}

int find(int x)
{
    return x==fa[x]? x:fa[x]=find(fa[x]);
}

signed main()
{
    int u, v, w;
    while (cin>>c>>n>>m)
    {
        init();
        for (int i=1;i<=n;i++)
        {
            cin>>u>>v>>w;
            if (vis[u][v]!=0)
                vis[u][v] = min(vis[u][v], w);
            else
            {
                vis[u][v] = w;
                a[++cnt] = make_pair(u, v);
            }
        }
        for (int i=1;i<=cnt;i++)
        {
            edge[i].u = a[i].first;
            edge[i].v = a[i].second;
            edge[i].w = vis[a[i].first][a[i].second];
        }
        sort(edge + 1, edge + cnt + 1, cmp);
        //采用克鲁斯卡尔算法去求最小生成树。
        //克鲁斯卡尔算法的原理在于不加考虑的加边，但是需要用并查集去检查是否产生回路。
        //并查集保存点，每选取一个边去检查两端的点是否在并查集里面是同一个集合。如果是就不加入到结果当中，
        //遍历每一条边
        for (int i=1;i<=cnt;i++)
        {
            int u = edge[i].u;
            int v = edge[i].v;
            int w = edge[i].w;
            int rootu = find(u);
            int rootv = find(v);
            if (rootu==rootv) continue;
            ans += w;
            num++;
            fa[rootu] = rootv;
        }
//         cout<<ans<<" "<<num<<endl;
        if (ans<=c&&num>=m-1) cout<<"Yes\n";
        else cout<<"No\n";
    }
    
    return 0;
}