NC17509 挖沟
题意：
给定n个点，m条边，每个边有一个花费，要求使得任意两个点都连通，并且建立若干条边使得 
最小，求至少需要多少花费满足题目所述
做法：
首先第一个条件，任意两个点连通的最小花费，说明只能选n-1条边，再结合第二个条件可知只需要求一个最小生成树即可。最小生成树模板题，考虑并查集的方式来判断这条边是否还需要即可得到最小生成树
代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
struct node
{
int a;
int b;
int c;
}e[500005];
int que[100005];
void init()
{
for (int i = 1; i < 100005; i++)
que[i] = i;
}
int getf(int k)
{
return que[k] == k ? k : que[k] = getf(que[k]);
}
void merge(int a, int b)
{
que[getf(a)] = getf(b);
}
int main()
{
init();
int n, m;
sc("%d%d", &n, &m);
for (int i = 0; i < m; i++)
sc("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
sort(e, e + m, [](node q, node w) {
return q.c < w.c;
});
ll ans = 0;
for (int i = 0; i < m; i++)
{
if (getf(e[i].a) != getf(e[i].b))
{
merge(e[i].a, e[i].b);
ans += e[i].c;
}
}
pr("%lld\n", ans);
} 
投递美团等公司10个岗位 >