牛客练习赛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-18 10:39
门头沟学院 Java
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-15 17:32
点赞 评论 收藏
分享
评论
6
3
分享

创作者周榜

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