当前位置: 首页 > news >正文

AtCoder292 E 思维

题意:

给定一副n(n≤3000)n(n\leq 3000)n(n3000)个顶点,mmm条有向边的图,可以在图中添加有向边,求添加的最少边数,使得这副图满足:如果顶点aaa到顶点bbb有边,顶点bbbccc右有边,那么顶点aaa到顶点ccc也有边

Solution:

考虑一条单向链,按指向的方向按顺序是A,B,C,D,...A,B,C,D,...A,B,C,D,...

显然,A→B,B→CA\rightarrow B,B\rightarrow CAB,BC需要添加一条边A→CA\rightarrow CAC,此时A→C,C→DA\rightarrow C,C\rightarrow DAC,CD需要添加A→DA\rightarrow DAD。更一般的情况是,在从AAA出发能到达的顶点里,只有与AAA距离为1的不需要添加边,只需要和其他点建边即可,并查集不适合有向图,O(n)O(n)O(n)的搜索可以满足要求,每个顶点搜索一次,总复杂度O(n2)O(n^2)O(n2)

#include<iostream>
#include<vector>
#include<cstdlib>
#include<numeric>
#include<unistd.h>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<map>
#include<stack>
#include<utility>
#include<cctype>
#include<cassert>
#include<thread>
#include<bitset>
using namespace std;using ll=long long;
const int N=2e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;struct way {int to,next;
}edge[N<<1];
int cnt,head[N];void add(int u,int v) {edge[++cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;
}int n,m,dis[N],vis[N];int main() {#ifdef stdjudgefreopen("in.txt","r",stdin);auto TimeFlagFirst=clock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin>>n>>m;for(int i=1;i<=m;i++) {int u,v;cin>>u>>v;add(u,v);}int tot=0;queue<int>q;for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) vis[j]=false;while(!q.empty()) q.pop();q.push(i);while(!q.empty()) {int u=q.front(); q.pop();vis[u]=true;for(int j=head[u];j;j=edge[j].next) {int v=edge[j].to;if(vis[v]) continue;q.push(v);}}for(int j=1;j<=n;j++) {if(i!=j&&vis[j]) tot++;}for(int j=head[i];j;j=edge[j].next) tot--;}cout<<tot<<endl;#ifdef stdjudgefreopen("CON","r",stdin);std::cout<<std::endl<<"耗时:"<<std::clock()-TimeFlagFirst<<"ms"<<std::endl;std::cout<<std::flush;system("pause");#endifreturn 0;
}

相关文章:

AtCoder292 E 思维

题意&#xff1a; 给定一副n(n≤3000)n(n\leq 3000)n(n≤3000)个顶点&#xff0c;mmm条有向边的图&#xff0c;可以在图中添加有向边&#xff0c;求添加的最少边数&#xff0c;使得这副图满足&#xff1a;如果顶点aaa到顶点bbb有边&#xff0c;顶点bbb到ccc右有边&#xff0c;…...

20230309英语学习

What Is Sleep Talking? We Look at the Science 为什么人睡觉会说梦话&#xff1f;来看看科学咋说 Nearly everyone has a story about people talking in their sleep.Though it tends to be more common in children, it can happen at any age:A 2010 study in the jour…...

CAD转换PDF格式怎么弄?教你几种方法轻松搞定!

CAD是从事与艺术创作相关等行业的打工人们必需的工作软件&#xff0c;可以用来完成建筑设计图、设计图纸等。在日常的工作中&#xff0c;一些伙伴经常需要传输图纸给合作方来完成探讨。但是CAD图纸需要使用专业软件才能打开&#xff0c;这就给文件传送带来了一定的困难。而且传…...

AtCoder 259E LCM

题意&#xff1a; 以唯一分解形式给出nnn个数&#xff1a; aipi,1ei,1pi,2ei,2...pi,tei,ta_{i}p_{i,1}^{e_{i,1}}p_{i,2}^{e_{i,2}}...p_{i,t}^{e_{i,t}} ai​pi,1ei,1​​pi,2ei,2​​...pi,tei,t​​ 现在可以将某个数改为111&#xff0c;求所有改法中&#xff0c;有多少个…...

MQTT协议-取消订阅和取消订阅确认

MQTT协议-取消订阅和取消订阅确认 客户端向服务器取消订阅 取消订阅的前提是客户端已经通过CONNECT报文连接上服务器&#xff0c;并且订阅了一个主题 UNSUBSCRIBE—取消订阅 取消订阅的报文同样是由固定报头可变报头有效载荷组成 固定报头由两个字节组成&#xff0c;第一个…...

90后小伙,用低代码“整顿”旅游业,年入2000万,他是怎么做到的?

热爱旅游的92年成都小伙猴哥&#xff0c;大学毕业后开了一家旅行社&#xff0c;主要从事川藏、云南定制游服务。 从今年春节开始&#xff0c;国内各地旅游业开始复苏&#xff0c;向旅行社打电话咨询的人越来越多。 旅游的人多是好事&#xff0c;也是一种烦恼&#xff0c;因为…...

C51---PWM 脉冲宽度调制

1.PWM:脉冲宽度调制,它是通过一系列脉冲宽度进行调制&#xff0c;等效出所需要的波形&#xff08;包含形状以及幅值&#xff09;。对模拟信号电平进行数字编码。也就是说通过调节占空比的变化来调节信号、能量等的变化&#xff0c;占空比就是指在一个周期内&#xff0c;信号处于…...

毕业设计 基于51单片机WIFI智能家居系统设计

基于51单片机WIFI智能家居系统设计1、毕业设计选题原则说明&#xff08;重点&#xff09;2、项目资料2.1 系统框架2.2 系统功能3、部分电路设计3.1 STC89C52单片机最小系统电路设计3.2 ESP8266 WIFI电路设计3.3 DHT11温湿度传感器电路设计4、部分代码展示4.1 LCD12864显示字符串…...

Nginx服务优化措施与配置防盗链

目录 一.优化Nginx的相关措施 二.隐藏/查看版本号 三.修改用户与组 四.设置缓存时间 五.日志切割脚本 六.设置连接超时控制连接访问时间 七.开启多进程 八.配置网页压缩 九.配置防盗链 1.配置web源主机&#xff08;192.168.79.210 www.zhuo.com&#xff09; 1.1 安装…...

Java 某厂面试题真题合集

哈喽~大家好&#xff0c;这篇来看看Java 某厂面试题真题合集。 &#x1f947;个人主页&#xff1a;个人主页​​​​​ &#x1f948; 系列专栏&#xff1a;【日常学习上的分享】 &#x1f949;与这篇相关的文章&#xff1a; Spr…...

很特别的5G市场,5.75亿部手机,却有11亿5G用户,这是怎么了?

中国在5G商用方面已取得了巨大的成绩&#xff0c;这是毋庸置疑的&#xff0c;不过近期公布的一份数据却相当特别&#xff0c;5G手机用户数为5.75亿&#xff0c;而开通了5G套餐的用户数却已超过11亿&#xff0c;这数据对比有点意思。中国在5G商用方面推进很快&#xff0c;建成的…...

go modules

文章目录1. 简介示例1. 示例——同一项目2. 示例——不同项目3. 示例——添加远程模块依赖库1. 简介 go module是Go1.11版本之后官方推出的版本管理工具&#xff0c;并且从Go1.13版本开始&#xff0c;go module将是Go语言默认的依赖管理工具。到今天Go1.14版本推出之后Go modu…...

Baklib客户故事:快递助手ERP

快递助手ERP以多平台多店铺订单管理为核心&#xff0c;集打单发货、商品、库存、采购、售后于一体&#xff0c;中小商家易上手的轻量级ERP&#xff0c;可以满足满足微商、自建商城、档口货源网、一件代发等不同类型客户的打单需求&#xff0c;通过开放平台API接口&#xff0c;自…...

MongoDB学习(java版)

MongoDB概述 结构化数据库 ​ 结构化数据库是一种使用结构化查询语言&#xff08;SQL&#xff09;进行管理和操作的数据库&#xff0c;它们的数据存储方式是基于表格和列的。结构化数据库要求数据预先定义数据模式和结构&#xff0c;然后才能存储和查询数据。结构化数据库通常…...

RK3568平台开发系列讲解(显示篇)什么是DRM

🚀返回专栏总目录 文章目录 一、DRM介绍二、DRM与framebuffer的区别沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇文章将介绍什么是DRM。 一、DRM介绍 DRM 是 Linux 目前主流的图形显示框架,相比FB架构,DRM更能适应当前日益更新的显示硬件。 比如FB原生不支…...

Python蓝桥杯训练:基本数据结构 [二叉树] 上

Python蓝桥杯训练&#xff1a;基本数据结构 [二叉树] 上 文章目录Python蓝桥杯训练&#xff1a;基本数据结构 [二叉树] 上一、前言二、有关二叉树理论基础1、二叉树的基本定义2、二叉树的常见类型3、二叉树的遍历方式三、有关二叉树的层序遍历的题目1、[二叉树的层序遍历](http…...

vuex基础之初始化功能、state、mutations、getters、模块化module的使用

vuex基础之初始化功能、state、mutations、getters、模块化module的使用一、Vuex的介绍二、初始化功能三、state3.1 定义state3.2 获取state3.2.1 原始形式获取3.2.2 辅助函数获取(mapState)四、mutations4.1 定义mutations4.2 调用mutations4.2.1 原始形式调用($store)4.2.2 辅…...

WebSphere中间件漏洞总结

WebSphere中间件漏洞总结 一、WebSphere简介 WebSphere为SOA(面向服务架构)环境提供软件,以实现动态的、互联的业务流程,为所有业务情形提供高度有效的应用程序基础架构。WebSphere是IBM的应用程序和集成软件平台,包含所有必要的中间件基础架构(包括服务器、服务和工具)…...

Unity之ASE实现影魔灵魂收集特效

前言 我们今天来实现一下Dota中的影魔死亡后&#xff0c;灵魂收集的特效。效果如下&#xff1a; 实现原理 1.先添加一张FlowMap图&#xff0c;这张图的UV是根据默认UV图&#xff0c;用PS按照我们希望的扭曲方向修改的如下图所示&#xff1a; 2.通过FlowMap图&#xff0c;我…...

半入耳式耳机运动会不会掉、佩戴超稳固的运动耳机推荐

现在越来越多的人开始意识到运动的重要性&#xff0c;用运动给身体增加一道“防护墙”是最好的生活方式了&#xff0c;不过&#xff0c;日复一日做着几乎相同的动作&#xff0c;难免索然无味&#xff0c;所以很多人都会选择在运动时戴上耳机听歌解闷&#xff0c;这时候也有不少…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...