牛客练习赛69 C
旅行
https://ac.nowcoder.com/acm/contest/7329/C
分析
考虑一个最大生成树，变化为序列之后一定有一种方案满足 。所以这道题只需要求一个最大生成树即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5+1000;
struct E{LL x,y,w;}e[N];
LL f[N],n,m;
LL find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
bool cmp(E a,E b){return a.w > b.w;}
int main()
{
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1;i <= n;i++) f[i] = i;
for(int i = 1;i <= m;i++) {
cin >> e[i].x >> e[i].y >> e[i].w;
}
sort(e+1,e+1+m,cmp);
LL ans = 0;
for(int i = 1;i <= m;i++) {
int fx = find(e[i].x),fy = find(e[i].y);
if(fx == fy) continue;
ans += e[i].w;
f[fx] = fy;
}
cout << ans << endl;
}
查看30道真题和解析
