NC15108 道路建设
题意：
给定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");
} 
字节跳动公司氛围 534人发布
查看6道真题和解析