食物链之带权并查集解法

直接看题:https://www.acwing.com/problem/content/description/242/

下面就是代码的实现了,因为自己与自己肯定是同类我们初始化为0.

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,k;
int fk,x,y;
int fa[100010],d[100010];
int find(int x)
{
    if(fa[x]!=x)
    {
        int t=fa[x];
        fa[x]=find(fa[x]);
        d[x]+=d[t];

    }
    return fa[x];
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) fa[i]=i;
    int res=0;
    while(k--)
    {
        cin>>fk>>x>>y;
        if(x>n||y>n) res++;
        else if(fk==1)
        {
            int x1=find(x),y1=find(y);
            if(x1==y1&&(d[x]-d[y])%3) res++;
            else if(x1!=y1)
            {
                fa[x1]=y1;
                d[x1]=d[y]-d[x]+3;
            }
        }
        else{
            int x1=find(x),y1=find(y);
            if(x1==y1&&(d[x]-d[y]-1)%3) res++;
            else if(x1!=y1)
            {
                fa[x1]=y1;
                d[x1]=d[y]-d[x]+4;
            }
        }
    }
    cout<<res;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790480.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++ STL IO流介绍

目录 一&#xff1a;IO流的继承关系&#xff1a; 二&#xff1a;输入输出功能 1. 基本用法 2. 格式化输入 3.非格式化输入 4. 格式化输出 三&#xff1a;流 1. 字符流 2. 向字符流中写入数据 3. 从字符流中读出数据 4. 清空字符流 5.完整的例子 四&#xff1a;文件…

RISC-V异常处理流程概述(2):异常处理机制

RISC-V异常处理流程概述(2):异常处理机制 一、异常处理流程和异常委托1.1 异常处理流程1.2 异常委托二、RISC-V异常处理中软件相关内容2.1 异常处理准备工作2.2 异常处理函数2.3 Opensbi系统调用的注册一、异常处理流程和异常委托 1.1 异常处理流程 发生异常时,首先需要执…

生物打印后的生物力学过程

生物打印后的生物力学过程 3D生物打印技术在组织工程领域展现出巨大的潜力&#xff0c;但打印后组织的生物力学特性对其最终成功至关重要。本文将详细介绍打印后组织的生物力学特性及其在组织工程中的应用。 1. 打印后水凝胶交联 原位交联可以在生物打印过程中提供足够的机械…

开发个人Go-ChatGPT--5 模型管理 (一)

开发个人Go-ChatGPT–5 模型管理 (一) 背景 开发一个chatGPT的网站&#xff0c;后端服务如何实现与大模型的对话&#xff1f;是整个项目中开发困难较大的点。 如何实现上图的聊天对话功能&#xff1f;在开发后端的时候&#xff0c;如何实现stream的响应呢&#xff1f;本文就…

SprintBoot创建遇到的问题

最近使用IDEA版本为2022.3.1&#xff0c;java版本为21.0.3&#xff0c;现在做一个创建SprintBoot3的一个大体流程 1.先下载Maven&#xff0c;解压到一个位置 maven下载 2.配置setting.xml文件 这路径自己配置&#xff0c;这里不多演示 代码如下&#xff1a; <mirror>&…

开源网页终端webssh容器镜像制作与使用

1.Dockerfile编写&#xff1a; # 指定镜像目标平台与镜像名 alpine表示基础镜像 第一层镜像 FROM --platform$TARGETPLATFORM alpine # 添加元数据到镜像 LABEL maintainer"Jrohy <euvkzxgmail.com>" # 编译时变量 ARG TARGETARCH # 执行编译命令&#xff0c;…

代码随想录算法训练营第四十九天| 647. 回文子串、 516.最长回文子序列

647. 回文子串 题目链接&#xff1a;647. 回文子串 文档讲解&#xff1a;代码随想录 状态&#xff1a;不会 思路&#xff1a; dp[i][j] 表示字符串 s 从索引 i 到索引 j 这一段子串是否为回文子串。 当s[i]与s[j]不相等&#xff0c;那没啥好说的了&#xff0c;dp[i][j]一定是fa…

柔性测斜仪:监测钻孔位移的核心利器

柔性测斜仪&#xff0c;作为一款创新的测量工具&#xff0c;凭借其卓越的设计与性能&#xff0c;在地下建筑、桥梁、隧道及水利水电工程等领域展现出非凡的应用价值。其安装便捷、操作简便、高精度及长寿命等特性&#xff0c;使之成为监测钻孔垂直与水平位移的理想选择。以下是…

打卡第8天-----字符串

进入字符串章节了,我真的特别希望把leetcode上的题快点全部都给刷完,我是社招准备跳槽才选择这个训练营的,面试总是挂算法题和编程题,希望通过这个训练营我的算法和编程的水平能有所提升,抓住机会,成功上岸。我现在的这份工作,真的是一天都不想干了,但是下家工作单位还…

VS Code 扩展如何发布到私有Nexus的正确姿势

VS Code扩展的发布 VS Code 扩展的发布需要使用到vsce&#xff0c;vsce是一个用于打包、发布和管理 VS Code 扩展的命令行工具。可以通过 npm 来全局安装它&#xff1a; npm install -g vsce发布扩展到微软的应用市场 VS Code 的应用市场基于微软自己的 Azure DevOps。要发布…

计算机网络--tcpdump和iptable设置、内核参数优化策略

tcpdump工具 tcpdump命令&#xff1a; 选项字段&#xff1a; 过滤表达式&#xff1a; 实用命令&#xff1a; TCP三次握手抓包命令&#xff1a; #客户端执行tcpdump 抓取数据包 tcpdump -i etho tcp and host 192.168.12.36 and port 80 -W timeout.pcapnetstat命令 netst…

element el-table实现表格动态增加/删除/编辑表格行,带校验规则

本篇文章记录el-table增加一行可编辑的数据列&#xff0c;进行增删改。 1.增加空白行 直接在页面mounted时对form里面的table列表增加一行数据&#xff0c;直接使用push() 方法增加一列数据这个时候也可以设置一些默认值。比如案例里面的 产品件数 。 mounted() {this.$nextTi…

[嵌入式 C 语言] 按位与、或、取反、异或

若协议中如下图所示&#xff1a; 注意&#xff1a; 长度为1&#xff0c;表示1个字节&#xff0c;也就是0xFF&#xff0c;也就是 1111 1111 &#xff08;这里0xFF只是单纯表示一个数&#xff0c;也可以是其他数&#xff0c;这里需要注意的是1个字节的意思&#xff09; 一、按位…

URI:URL、URN

名称解释&#xff1a; URI:统一资源标识符&#xff1b; URL:统一资源定位符; URN:统一资源命名符&#xff1b; URI、URL、URN关系 URI是URL和URN的超集,也就是说URI有两种方式&#xff0c;一种是URL一种是URN,不过URL的方式用的比较多。 看了一个视频&#xff0c;博主解释非…

xcode配置swift使用自定义主题颜色或者使用RGB或者HEX颜色

要想在xcode中使用自定义颜色或者配置主题色&#xff0c;需要在Assets中配置&#xff0c;打开Assets文件&#xff0c;然后点击添加Color Set&#xff1a; 输入颜色的名称&#xff0c;然后选中这个颜色&#xff0c;会出现两个颜色&#xff1a; Any Appearance表示亮色模式下使用…

基于uni-app与图鸟UI的知识付费小程序模板

一、项目概述 在知识经济蓬勃发展的背景下&#xff0c;移动互联网成为知识传播与消费的重要渠道。本项目旨在利用前沿的前端技术栈——uni-app及高效UI框架图鸟UI&#xff0c;打造一款集多功能于一体的、面向广大求知者的知识付费平台移动端模板。该模板旨在简化开发流程&…

【最强八股文 -- 计算机网络】【快速版】TCP 与 UDP 头部格式

目标端口和源端口: 应该把报文发给哪个进程包长度: UDP 首部的长度跟数据的长度之和校验和: 为了提供可靠的 UDP 首部和数据而设计&#xff0c;接收方使用检验和来检查该报文段中是否出现差错 源端口号和目的端口号: 用于多路复用/分解来自或送到上层应用的数据。告诉主机报文段…

轻松理解c++17的string_view

文章目录 轻松理解c17的string_view设计初衷常见用法构造 std::string_view常用操作作为函数参数 注意事项总结 轻松理解c17的string_view std::string_view 是 C17 引入的一个轻量级、不拥有&#xff08;non-owning&#xff09;的字符串视图类。它的设计初衷是提供一种高效、…

Web学习day03

maven&Mybatis 目录 maven&Mybatis 文章目录 一、maven 1.1作用 1.2仓库 1.3命令 1.4依赖范围 1.5生命周期 二、MyBatis 2.1简介 2.2API 2.3增删改的实现&案例 总结 一、maven 1.1作用 统一项目结构&#xff1b;项目构建&#xff1a;通过简单命令&a…

高阶面试-dubbo的学习

SPI机制 SPI&#xff0c;service provider interface&#xff0c;服务发现机制&#xff0c;其实就是把接口实现类的全限定名配置在文件里面&#xff0c;然后通过加载器ServiceLoader去读取配置加载实现类&#xff0c;比如说数据库驱动&#xff0c;我们把mysql的jar包放到项目的…