题意:

给定n个点,m条边,每个边有一个代价,判断这n个点能否变成一个连通图,并且要求代价小于等于 k

做法:

最小生成树模板题,考虑并查集的方式来判断这条边是否还需要即可

代码:

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
struct edge
{
    int a;
    int b;
    int c;
}e[10005];
int que[10005];
int getf(int k)
{
    return que[k] == k ? k : que[k] = getf(que[k]);
}
int main()
{
    for (int i = 1; i < 10005; i++)
        que[i] = i;
    int cost, n, m;
    sc("%d%d%d", &cost, &m, &n);
    for (int i = 0; i < m; i++)
        sc("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e, e + m, [](edge q, edge w) {
        return q.c < w.c;
        });
    ll ans = 0;
    for (int i = 0; i < m; i++)
    {
        int f1 = getf(que[e[i].a]);
        int f2 = getf(que[e[i].b]);
        if (f1 != f2)
        {
            que[f1] = f2;
            ans += e[i].c;
        }
    }
    if (ans <= cost)
        pr("Yes\n");
    else
        pr("No\n");
}