首页 > 其他分享 >毁灭PTA

毁灭PTA

时间:2023-11-29 16:58:00浏览次数:30  
标签:int res 边权 毁灭 long PTA

毁灭PTA

image

思路:

一道比较简单的最小生成树的应用,因为他的边权存在负值,而我们又想要得到最大分数,事实上我们就只需要统计一下正数的总和以及我们在建树时候用到了多少正数边权就可以巧妙地解决这个问题

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int fa[N];
struct node
{
    int a,b,c;

}f[N];
int n,m;
void init(){
    for(int i=1;i<=N;i++){
        fa[i]=i;
    }
}//并查集的初始化
int find(int x){//并查集的查找与合并
    if(fa[x]==x){
        return x;

    }
    else{
        return fa[x]=find(fa[x]);

    }
}
bool cmp(node x,node y){
    return x.c<y.c;

}
void solve(){
    init();//初始化
    cin>>n>>m;
    // int l=1;
    int sum=0;

    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(w>0){
            sum+=w;

        }

        f[i]={u,v,w};

    }
    int cnt=0;
    int res=0;
    sort(f+1,f+m+1,cmp);
    for(int i=1;i<=m;i++){
        auto it=f[i];
        int x1=it.a;
        int y1=it.b;
        if(find(x1)!=find(y1)){
            fa[find(x1)]=fa[find(y1)];
            cnt++;//边数加
            if(it.c>0){
                res+=it.c;
                
            }
        }
    }
    // cout<<cnt<<" "<<res<<endl;
    // return ;
    
    //最小生成树一定是只有n-1条边
    //虽然我们建好树了,但是有些边其实也可以不用被毁掉,不然得分还是会少

    cout<<sum-res<<endl;
    return ;
    
}
signed main(){
    int t=1;
    while(t--){
        solve();
    }
    return 0;

}

标签:int,res,边权,毁灭,long,PTA
From: https://www.cnblogs.com/du463/p/17865272.html

相关文章

  • PTA 感染人数
    7-1感染人数作者 黄龙军单位 绍兴文理学院设某住宿区域是一个n×n的方阵,方阵中的每个小方格为一个房间,房间里可能住一个人,也可能空着。第一天,某些房间中住着的人得了一种高传染性的流感,以后每一天,得流感的人会使其邻居(住在其上、下、左、右方向存在的房间里面的人)传染上......
  • java.lang.ClassNotFoundException: javax.servlet.jsp.jstl.core.LoopTag问题的解决
    问题描述问题解决将这个依赖:改成这个依赖:......
  • iptables 杂谈ACCEPT和RETURN
    iptables杂谈ACCEPT和RETURN这两个目标,确实比较模糊。目录iptables杂谈ACCEPT和RETURN实验结论实验这里是实验的情况:新建两个iptables的规则链,并且相连,如果是ACCEPT:-Nmy_rule_1-Nmy_rule_2-Amy_rule_1-jACCEPT-Amy_rule_2-jACCEPT-Aparental_ctrl_0-jmy_......
  • PTA-ch7b-5 : 最小工期
    最小工期一个项目由若干个任务组成,任务之间有先后依赖顺序。项目经理需要设置一系列里程碑,在每个里程碑节点处检查任务的完成情况,并启动后续的任务。现给定一个项目中各个任务之间的关系,请你计算出这个项目的最早完工时间。输入格式:首先第一行给出两个正整数:项目里程碑的数量N......
  • 第八章iptables防火墙
    安装iptables服务保存不上,可能没安装iptables服务yuminstalliptables-services.x86_64关闭防火墙systemctlstopfirewalldsystemctlmaskfirewalld2安装iptables服务yuminstalliptables-services3设置iptables服务开机启动systemctlenableiptables4重启iptab......
  • Docker启动失败,提示"iptables: No chain/target/match by that name"
    一、问题现象docker容器报错:docker:Errorresponsefromdaemon:driverfailedprogrammingexternalconnectivityonendpointetlmysql(12ccdbcef942bef6f32dbfc157dd1b49319ee2df4d68bf7b9a9b9ea88b5bd4fa):(iptablesfailed:iptables--wait-tnat-ADOCKER-ptc......
  • linux iptables初步理解
    引用:https://www.bilibili.com/video/BV1Jz4y1u7Lz/?spm_id_from=333.788&vd_source=e05f4a55dd5d8e27f74472aa7fd97ace1.iptables处理模型:linux内核有一个netfilter框架来设置这个防火墙linux可以像路由器一样做转发处理的,所以流量处理就有如下路径:iptables有四......
  • firewalld与iptables区别
    ComparisonofFirewalldtosystem-config-firewallandiptablesTheessentialdifferencebetweenfirewalldandiptablesserviceare:Theiptablesservicestoresconfigurationin/etc/sysconfig/iptableswhilefirewalldstoresitinvariousXMLfilesin/u......
  • PTA题目集4、5、6以及期中考试的总结
    一、前言在过去做完的PTA题目集4、5、6以及期中考试,相比前几次的题目集来说难度都相对提高了许多,对于基础相对比较薄弱的我做起来也比较吃力,但是题量比之前都少了很多,后两次题目集都只有菜单计价程序一题,最主要的也还是菜单计价程序这一类题目,代码量很大。这类题目对于类的考察......
  • pta博客二
    前言在这次pta题目集4~6中,我们有了前三次基础java作业的基础,正式开始对java实验的进阶,其中的菜单计价程序的难度逐渐增大,第五次和第六次pta作业都是在第四次作业菜单计价程序-三上进行添加的,难度有点大。在这三次题目集当中,因为对于java函数的使用不算熟练,有些函数实现的代码还......