牛客练习赛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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 12:10
点赞 评论 收藏
分享
昨天 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
评论
6
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务