首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

bzoj1515[POI2006]LisThePostman有向图欧拉回路

作者：hh呢喃_845 | 来源：互联网 | 2023-07-20 14:40
LINK：LisThePostman看完题觉得虽然容易发现是有向图欧拉回路但是觉得很难解决这个问题。先分析一下有向图的欧拉回路：充要条件图中每个点的入度出度0且整张图是一个强连通分

LINK：Lis-The Postman

看完题觉得 虽然容易发现是有向图欧拉回路 但是觉得很难解决这个问题。

先分析一下有向图的欧拉回路：充要条件 图中每个点的入度-出度=0且整张图是一个强连通分量。

证明：首先考虑前者 这个思想是 从一个点出去必然还能回来所以可以形成回路 后者保证了图是联通的。

但是注意观察题目中有一些比较好的条件 每两个点之间的边最多有两条且方向不同。

题目给了k条必须要要连续走的路径 容易想到多条路径可以合并在一起。

这个操作看起来难做 但是 把边进行标号 然后只需要前驱和后继进行合并即可。

判定条件：1 图中原本的点入度-出度=0.2 一条边在一条路径出现两次就是错的 3 一条边有多个前驱后继就是错的。

这样 我们可以把一些边给合并起来了。我们可以要求一走走完这些边。

4 这些边合并在一起后 存在环了那么肯定也走不了。

剩下的就是一个正常的图了 跑欧拉回路即可。

5 在新建的图中再次判断点的出度和入度。

6 最后需要判断图联通与否。

7 判断是否可以从1出发

8 虽然没要求输出方案但是这里点一下 倒序输出点 点和点相连就是边了 更快的方法 输出点的时候可以直接记录将这个点送进来的边是哪个直接输出边。

//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define db double
#define INF 1000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define pii pair
#define mk make_pair
#define RE register
#define P 1000000007
#define S second 
#define F first
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ull unsigned long long
#define ui unsigned
#define EPS 1e-8
#define mod 1000000007
#define sq sqrt
#define l(p) t[p].l
#define r(p) t[p].r
#define op(p) t[p].op
#define cnt(p) t[p].cnt
#define sum(p) t[p].sum
#define zz p<<1
#define yy p<<1|1
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    RE int x=0,f=1;RE char ch=getc();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getc();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getc();}
    return x*f;
}
const int MAXN=200010,maxn=50010;
int n,m,len,k,top;
int du[MAXN],w[MAXN],b[MAXN],s[MAXN];
mapH[maxn];
struct wy{int x,y;}t[MAXN];
int pre[MAXN],ne[MAXN],vis[MAXN];
int lin[MAXN],ver[MAXN],nex[MAXN],fir[MAXN];
inline void add(int x,int y,int w1)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
    ++du[x];--du[y];
    fir[len]=w1;
    //cout<

bzoj 1515 [POI2006]Lis-The Postman 有向图欧拉回路
推荐阅读
  • php

    华为云对象存储系统配置指南

    本指南详细介绍了如何利用华为云对象存储服务构建视频点播（VoD）平台。通过结合开源技术如Ceph、WordPress、PHP和Nginx，用户可以高效地实现数据存储、内容管理和网站搭建。主要内容涵盖华为云对象存储系统的配置步骤、性能优化及安全设置，为开发者提供全面的技术支持。 ... [详细]
  • php

    深入解析：Synchronized 关键字在 Java 中对 int 和 Integer 对象的作用与影响

    深入解析：Synchronized 关键字在 Java 中对 int 和 Integer 对象的作用与影响
    深入探讨了 `Synchronized` 关键字在 Java 中对 `int` 和 `Integer` 对象的影响。尽管初看此题似乎简单，但其实质在于理解对象的概念。根据《Java编程思想》第二章的观点，一切皆为对象。本文详细分析了 `Synchronized` 关键字在不同数据类型上的作用机制，特别是对基本数据类型 `int` 和包装类 `Integer` 的区别处理，帮助读者深入理解 Java 中的同步机制及其在多线程环境中的应用。 ... [详细]
  • php

    Unity3D 中 AsyncOperation 实现异步场景加载及进度显示优化技巧

    Unity3D 中 AsyncOperation 实现异步场景加载及进度显示优化技巧
    在Unity3D中，通过使用`AsyncOperation`可以实现高效的异步场景加载，并结合进度条显示来提升用户体验。本文详细介绍了如何利用`AsyncOperation`进行异步加载，并提供了优化技巧，包括进度条的动态更新和加载过程中的性能优化方法。此外，还探讨了如何处理加载过程中可能出现的异常情况，确保加载过程的稳定性和可靠性。 ... [详细]
  • testing

    如何在Conda环境中高效配置并安装PyTorch与TensorFlow GPU版

    在Conda环境中高效配置并安装PyTorch和TensorFlow GPU版的方法如下：首先，创建一个新的Conda环境以避免与基础环境发生冲突，例如使用 `conda create -n pytorch_gpu python=3.7` 命令。接着，激活该环境，确保所有依赖项都正确安装。此外，建议在安装过程中指定CUDA版本，以确保与GPU兼容性。通过这些步骤，可以确保PyTorch和TensorFlow GPU版的顺利安装和运行。 ... [详细]
  • php

    E. DeadLee：思维导图与拓扑结构的深度解析

    题目 E. DeadLee：思维导图与拓扑结构的深度解析问题描述：给定 n 种食物，每种食物的数量由 wi 表示。同时，有 m 位朋友，每位朋友喜欢两种特定的食物 x 和 y。目标是通过合理分配食物，使尽可能多的朋友感到满意。本文将通过思维导图和拓扑排序的方法，对这一问题进行深入分析和求解。 ... [详细]
  • php

    VS2019 在创建 Windows 恢复点时出现卡顿问题及解决方法

    VS2019 在创建 Windows 恢复点时出现卡顿问题及解决方法
    在使用 Visual Studio 2019 时，有时会在创建 Windows 恢复点时遇到卡顿问题。这可能是由于频繁的自动更新导致的，每次更新文件大小可能达到 1-2GB。尽管现代网络速度较快，但这些更新仍可能对系统性能产生影响。本文将探讨该问题的原因，并提供有效的解决方法，帮助用户提升开发效率。 ... [详细]
  • php

    飞秋软件的OA消息接口服务系统

    为了提升单位内部沟通效率，我们开发了一套飞秋软件与OA系统的消息接口服务系统。该系统能够将OA系统中的审批、通知等信息自动同步至飞秋平台，确保员工在使用飞秋进行日常沟通的同时，也能及时获取OA系统的各类重要信息，从而实现无缝对接，提高工作效率。 ... [详细]
  • php

    深入解析浏览器内核与版本的发展历程

    浏览器作为我们日常不可或缺的软件工具，其背后的运作机制却鲜为人知。本文将深入探讨浏览器内核及其版本的演变历程，帮助读者更好地理解这一关键技术组件，揭示其内部运作的奥秘。 ... [详细]
  • default

    如何在 Vim 编辑器中调整和自定义配色方案

    Vim 编辑器功能强大，但其默认的配色方案往往不尽如人意，尤其是注释颜色为蓝色时，对眼睛极为不友好。为了提升编程体验，自定义配色方案显得尤为重要。通过合理调整颜色，不仅可以减轻视觉疲劳，还能显著提高编码效率和兴趣。 ... [详细]
  • php

    跨线程调用UI控件方法的invoke机制总结与优化建议

    在跨线程调用UI控件方法时，通常使用同步调用机制，如 `控件.Invoke(Delegate, 参数)`。这里需要声明并实现一个委托，因为控件本身并不知道如何处理跨线程操作。通过将具体的实现逻辑封装在委托中，控件可以正确地执行这些操作，确保线程安全性和UI的一致性。此外，为了提高性能和可维护性，建议对频繁的跨线程调用进行优化，例如使用异步调用或批量处理请求。 ... [详细]
  • grid

    在各项条件尚未成熟时，务必谨慎使用border-box布局模式！！！

    近日，我在处理一个复杂的前端问题时遇到了极大困扰。具体来说，我之前开发了一个功能丰富的纯jQuery代码的前端GridView控件，实现了多种功能和视觉效果，并在多个项目中表现良好。然而，最近在尝试应用 `border-box` 布局模式时，却遇到了意想不到的兼容性和性能问题。这提醒我们在条件尚未完全成熟的情况下，应谨慎使用 `border-box` 布局模式，以免引入不必要的复杂性和潜在的bug。 ... [详细]
  • install

    【Eclipse开发效率提升插件推荐】利用Google V8增强Node.js调试体验

    在Eclipse中提升开发效率，推荐使用Google V8插件以增强Node.js的调试体验。安装方法有两种：一是通过Eclipse Marketplace搜索并安装；二是通过“Help”菜单中的“Install New Software”，在名称栏输入“googleV8”。此插件能够显著改善调试过程中的性能和响应速度，提高开发者的生产力。 ... [详细]
  • php

    深入解析Java虚拟机的内存分区与管理机制

    深入解析Java虚拟机的内存分区与管理机制
    Java虚拟机的内存分区与管理机制复杂且精细。其中，某些内存区域在虚拟机启动时即创建并持续存在，而另一些则随用户线程的生命周期动态创建和销毁。例如，每个线程都拥有一个独立的程序计数器，确保线程切换后能够准确恢复到之前的执行位置。这种设计不仅提高了多线程环境下的执行效率，还增强了系统的稳定性和可靠性。 ... [详细]
  • process

    Python 伦理黑客技术：深入探讨后门攻击（第三部分）

    Python 伦理黑客技术：深入探讨后门攻击（第三部分）
    在《Python 伦理黑客技术：深入探讨后门攻击（第三部分）》中，作者详细分析了后门攻击中的Socket问题。由于TCP协议基于流，难以确定消息批次的结束点，这给后门攻击的实现带来了挑战。为了解决这一问题，文章提出了一系列有效的技术方案，包括使用特定的分隔符和长度前缀，以确保数据包的准确传输和解析。这些方法不仅提高了攻击的隐蔽性和可靠性，还为安全研究人员提供了宝贵的参考。 ... [详细]
  • php

    深入解析Linux内核中的进程上下文切换机制

    深入解析Linux内核中的进程上下文切换机制
    在现代操作系统中，进程作为核心概念之一，负责管理和分配系统资源，如CPU和内存。深入了解Linux内核中的进程上下文切换机制，需要首先明确进程与程序的区别。进程是一个动态的执行流，而程序则是静态的数据和指令集合。进程上下文切换涉及保存当前进程的状态信息，并加载下一个进程的状态，以实现多任务处理。这一过程不仅影响系统的性能，还关系到资源的有效利用。通过分析Linux内核中的具体实现，可以更好地理解其背后的原理和技术细节。 ... [详细]
author-avatar
hh呢喃_845
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有