CF1494F Delete The Edges 题解

Description

给定一张 n n n 个点、 m m m 条边的图,你可以从图上任意一点出发,目标是删去所有的边,当一条边被删去后你不能再走此边。

初始模式下,一条边在你走过后会立即被删去。

你可以在任意一点切换模式(或全程不换),换完模式后走过的第偶数条便会被删去,且不可重新换回初始模式。

求一组方案。

Solution

观察样例可得切换模式后走的图为一个菊花图,下面浅浅分析一下。

假设只有一条边,则折返走一遍便能删完。

若为两条边 ( i , j ) , ( j , k ) (i,j),(j,k) (i,j),(j,k),发现只能 j → i → j → k → j j\rightarrow i\rightarrow j\rightarrow k\rightarrow j jijkj 将其删完。

依此类推,删边必须像 i → j → i i\rightarrow j\rightarrow i iji 折返地删。

所以我们可以枚举菊花图的中心,构造出走一条终点为菊花图中心的欧拉路径,然后切换模式的方案。

关键在于如何求出这条欧拉路径。

首先将所有和中心相连的奇点(度数为奇)和中心连的这条边删去,这样这个点就会变为偶点(度数为偶),方便后续操作。

然后得出当前图中奇点个数 c n t cnt cnt,和中心度数是否为 0 0 0,记为 f f f

f = t r u e f=true f=true

  • c n t > 2 cnt>2 cnt>2,无法构出欧拉路径,非法。

  • c n t = 2 cnt=2 cnt=2 且中心不为奇点,终点不为中心,非法。

  • c n t = 2 cnt=2 cnt=2 且外围图不连通(除去度数为 0 0 0 的点,这些点虽然不连通,但切换模式后都会连通),非法。

  • c n t = 2 cnt=2 cnt=2 且外围连通,即我们已经构造出了合法方案。

f = f a l s e f=false f=false

  • c n t ≥ 2 cnt\ge2 cnt2,还要连一条边到中心,然而再加边就不是欧拉路径了,非法。

剩下还剩当前路径有中心但外围不连通、当前路径不含中心两种情况,发现 c n t = 0 cnt=0 cnt=0 使得我们可以在加一条删去的边到欧拉路径上,那我们就枚举这条边。

首先当前外围图(此时是除去度数为 0 0 0 的点但此点不为中心)连通块个数要小于等于 2 2 2,因为加一条边只能让两个连通块连通。

然后分别将这两连通块染色,遍历删去的边,若边的两顶点颜色不同,则加上这条边,发现这种合法方案的起点就是这两顶点中不是中心的那个点。

发现一定存在这条先前被删去的边,即我们一定能找到合法方案。

然后我们按输出要求输出方案即可,首先遍历欧拉路径,再切换模式,然后折返删菊花图。

代码细节很多,理清思路再写。

时间复杂度 O ( n ( n + m ) ) O(n(n+m)) O(n(n+m))

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tot,head[3030];
int in[3030],du[3030],col[3030];
bool vis[3030],viss[3030],pit[3030];
vector<int> path;
struct edge{int to,next,id;
}e[6060];
void add(int x,int y,int z){e[++tot]=edge{y,head[x],z};head[x]=tot;
}
void dfs(int x,int v=0){viss[x]=1;col[x]=v;for(int i=head[x];i;i=e[i].next){int y=e[i].to,w=e[i].id;if(viss[y]||vis[w]) continue;dfs(y,v);}
}
void get(int x){bool f=0;int ss,ww;for(int i=head[x];i;i=e[i].next){int y=e[i].to,w=e[i].id;if(!vis[w]){vis[w]=1;get(y);path.push_back(x);}}
}
bool solve(int st){for(int i=1;i<=n;i++) du[i]=in[i],viss[i]=0,pit[i]=0,col[i]=0;for(int i=1;i<=m;i++) vis[i]=0;bool f=0;int ts=0,ttot=0;  //ts为方案起点、ttot为切换模式后删的边数for(int i=head[st];i;i=e[i].next){int y=e[i].to,w=e[i].id;if(du[y]%2){  //删去中心与偶点相连的边pit[y]=1,du[y]--,du[st]--,vis[w]=1,ttot++;}else f=1;  //中心是否在当前欧拉路径上}int cnt=0,fl=0;for(int i=1;i<=n;i++){if(du[i]%2) cnt++;  //奇点数量if(du[i]%2&&i!=st) fl=i;  //得出合法欧拉路径的起点}if(f){if(fl==0) fl=st;  //欧拉回路则任选起点if(cnt>2) return 0;if(cnt==2&&du[st]%2==0) return 0;if(cnt==2){dfs(st);for(int i=1;i<=n;i++){  //判断外围连通性if(du[i]==0) continue;if(!viss[i]) return 0;}ts=fl;}}else{if(cnt>=2) return 0;}if(cnt==0){dfs(st);  //染第一个连通块bool ff=0;for(int i=1;i<=n;i++){if(du[i]==0) continue;if(!viss[i]){if(ff) return 0;  //有至少三个连通块dfs(i,1);ff=1;}}if(ff){for(int i=head[st];i;i=e[i].next){int y=e[i].to,w=e[i].id;if(pit[y]&&col[y]){  //是之前删去的奇点且与中心不在同一连通块上pit[y]=0,vis[w]=0,ttot--;ts=y,du[y]++,du[st]++;break;}}}else{  //只有一个连通块即为欧拉回路ts=st;}}cout<<m+ttot+2<<'\n';  //m条边要删完则有m次操作,ttot条边被操作2次,加上起点和切换模式的2次操作get(ts);  //遍历欧拉路径for(int i=path.size()-1;i>=0;i--) cout<<path[i]<<" ";cout<<st<<" ";cout<<-1<<" ";for(int i=head[st];i;i=e[i].next){int y=e[i].to,w=e[i].id;if(pit[y]){cout<<y<<" "<<st<<" ";  //折返删菊花图}}return 1;
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;in[x]++,in[y]++;add(x,y,i),add(y,x,i);}for(int i=1;i<=n;i++){if(solve(i)){return 0;}}cout<<"0"<<'\n';  //无解return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

植物检测系统源码分享

植物检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vision …

Java面向对象——内部类(成员内部类、静态内部类、局部内部类、匿名内部类,完整详解附有代码+案例)

文章目录 内部类17.1概述17.2成员内部类17.2.1 获取成员内部类对象17.2.2 成员内部类内存图 17.3静态内部类17.4局部内部类17.5匿名内部类17.5.1概述 内部类 17.1概述 写在一个类里面的类叫内部类,即 在一个类的里面再定义一个类。 如&#xff0c;A类的里面的定义B类&#x…

闪回科技再冲刺上市:曾夸大融资规模,毛利率下滑,有股东退出

近日&#xff0c;闪回科技有限公司&#xff08;下称“闪回科技”&#xff09;递交招股书&#xff0c;准备在港交所主板上市。据贝多财经了解&#xff0c;该公司曾于2024年2月递表&#xff0c;此次是“失效”后的更新版本&#xff0c;清科资本为其独家保荐人。 闪回科技在招股书…

力扣刷题之815.公交路线

题干描述 给你一个数组 routes &#xff0c;表示一系列公交线路&#xff0c;其中每个 routes[i] 表示一条公交线路&#xff0c;第 i 辆公交车将会在上面循环行驶。 例如&#xff0c;路线 routes[0] [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 ->…

全国职业院校技能大赛(大数据赛项)-平台搭建Spark、Scala笔记

Spark作为一个开源的分布式计算框架拥有高效的数据处理能力、丰富的生态系统、多语言支持以及广泛的行业应用。Scala是一种静态类型的编程语言&#xff0c;它结合了面向对象编程和函数式编程的特性&#xff0c;被誉为通用的“大数据语言”。而二者的结合更能迸发出新奇的化学反…

Dify创建自定义工具,调用ASP.NET Core WebAPI时的注意事项(出现错误:Reached maximum retries (3) for URL ...)

1、要配置Swagger using Microsoft.AspNetCore.Mvc; using Microsoft.OpenApi.Models;var builder WebApplication.CreateBuilder(args);builder.Services.AddCors(options > {options.AddPolicy("AllowSpecificOrigin",builder > builder.WithOrigins("…

Transformers | 在自己的电脑上开启预训练大模型使用之旅!

本文内容主要包括两部分&#xff1a; Hugging Face 社区介绍 如何使用 Transformers 库的模型 1. Hugging Face 社区介绍 Hugging Face (https://huggingface.co/) 是一个 Hub 社区&#xff0c;它和 GitHub 相同的是&#xff0c;他们都是基于 Git 进行版本控制的存储库社区&…

SRS流媒体服务器在宝塔面板下的安装

目录 一、安装 1、安装Docker 2、安装srs 二、测试 1、进入后台 2、推流 3、播放测试: (1)网页 (2)拉流 之前一篇文章,我们介绍了SRS流媒体服务器在CentOS下的安装,安装流程还是比较麻烦且耗时的,其实SRS支持Docker部署,今天我们介绍在宝塔面板的Docker中部署…

【C++篇】~类和对象(中)

类和对象&#xff08;中&#xff09; 1.类的默认成员函数​ 默认成员函数就是用户没有显式实现&#xff0c;编译器会自动生成的成员函数称为默认成员函数。一个类&#xff0c;我们不写的情况下编译器会默认生成以下6个默认成员函数&#xff0c;需要注意的是这6个中最重要的是前…

深入探索PostgreSQL优化器的代价模型(建议收藏)

PawSQL优化引擎的实现深受PostgreSQL优化器的影响&#xff0c;本文我们来揭密PostgreSQL的代价模型。PawSQL专注于数据库性能优化自动化和智能化&#xff0c;提供的解决方案覆盖SQL开发、测试、运维的整个流程&#xff0c;广泛支持MySQL、PostgreSQL、OpenGauss、Oracle等主流商…

数据脱敏-快速使用

1.数据脱敏定义 数据脱敏百度百科中是这样定义的&#xff1a; 数据脱敏&#xff0c;指对某些敏感信息通过脱敏规则进行数据的变形&#xff0c;实现敏感隐私数据的可靠保护。 因为在真正的生产环境中,很多数据是不能直接返回,但是我们工作的时候可能经常性的需要返回一些用户信…

历年大厂校招 网络安全面试题(80+经验贴)

《网安面试指南》http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247484339&idx1&sn356300f169de74e7a778b04bfbbbd0ab&chksmc0e47aeff793f3f9a5f7abcfa57695e8944e52bca2de2c7a3eb1aecb3c1e6b9cb6abe509d51f&scene21#wechat_redirect 《Java代码审…

为什么要使用多线程

为什么要使用多线程 任务分解&#xff1a;耗时的操作&#xff0c;任务分解&#xff0c;实时响应。数据分解&#xff1a;充分利用多核CPU处理数据。数据流分解&#xff1a;读写分离&#xff0c;解耦合设计。 #include <iostream> #include<thread> using namespac…

【Unity编辑器扩展】解决uGUI动效痛点 零代码可视化快速制作UI动效 DOTween Sequence可视化

UI动效痛点&#xff1a; UI动效一直是Unity游戏开发的一大痛点&#xff0c;大部分项目都在使用Animator/Animation制作UI动效。而Animation是以节点路径记录动画&#xff0c;一旦UI层级、节点名变更就会导致动效返工&#xff0c;且Animation编辑器缓动曲线很难控制&#xff0c…

【论文速看】DL最新进展20240923-长尾综述、人脸防伪、图像分割

目录 【长尾学习】【人脸防伪】【图像分割】 【长尾学习】 [2024综述] A Systematic Review on Long-Tailed Learning 论文链接&#xff1a;https://arxiv.org/pdf/2408.00483 长尾数据是一种特殊类型的多类不平衡数据&#xff0c;其中包含大量少数/尾部类别&#xff0c;这些类…

C:内存函数

目录 前言&#xff1a; 一、memcpy 函数的使用及实现 1、memcpy函数的介绍 1.1 memcpy函数参数解读 2、memcpy函数的使用 3、memcpy函数的模拟实现 二、memmove函数的使用及模拟 1、memmove函数的使用 2、memmove函数的模拟实现 三、memset 函数的使用 1、memset函数的…

PyCharm下载和安装教程

Python、C/C、C#、DSL、Go、Groovy、Java、JavaScript、Objective-C、PHP 等编程语言。 图 1 JetBrains 开发工具 PyCharm下载和安装 进入 PyCharm官方下载页面(如图 2 所示)&#xff0c;可以看到 PyCharm 有 2 个版本&#xff0c;分别是 Professional(专业版)和 Community(社…

Mybatis百万数据插入(含导出)

1 一般一次性插入多条数据 传统的sql语句&#xff1a; INSERT INTO table1 ( field1, field2 ) VALUES( "data1", "data2" ); INSERT INTO table1 ( field1, field2 ) VALUES( "data1", "data2" ); INSERT INTO table1 ( field1, fi…

DirectX修复助手

在日常使用电脑时&#xff0c;我们可能会遇到提示缺少DLL文件&#xff0c;如0xc000007b错误、缺少d3dxxx.dll等问题&#xff0c;这些会影响软件运行甚至导致系统不稳定。以下是一些常见的DLL问题原因和一个修复工具&#xff0c;希望能帮到你。 DLL文件问题的常见原因 软件安装…

20 基于STM32的温度、电流、电压检测proteus仿真系统(OLED、DHT11、继电器、电机)

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于STM32F103C8T6 采用DHT11读取温度、滑动变阻器模拟读取电流、电压。 通过OLED屏幕显示&#xff0c;设置电流阈值为80&#xff0c;电流小阈值为50&#xff0c;电压阈值为60&#xff0c;温度阈值…