poj 2337 欧拉回路按照最小字典序输出+注意为了按最小字典序怎么处理邻接表

2024-05-28 04:58

本文主要是介绍poj 2337 欧拉回路按照最小字典序输出+注意为了按最小字典序怎么处理邻接表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://poj.org/problem?id=2337


WA了好久,昨晚1点多睡不着写的,狂WA,当时是因为用邻接矩阵存储,比如aba,aa只能存下一个,这个之前还没遇到过,今天才注意到--邻接矩阵无法存储平行边,  
关于欧拉回路判断看我另几篇日志或者看我的欧拉总结
再贴个输出欧拉回路的模板
其中,参数u是起点,注意如果是输出欧拉路径的话,u必须是出度比入度大一的那个点,如果输出欧拉回路,随便按要求找个就行

void euler(int u)
{for(int i=head[u];i!=-1;i=edge[i].next){if(!edge[i].vis){////cout << "caodan" << edge[i].to << endl;/edge[i].vis=1;euler(edge[i].to);path[ecnt++]=i;}}
}



这道题最重要的就是怎么输出字典序的最短路了

注意:
1、链式前向星(邻接表)是“后插式的”,比如aa.aba,即使你先加入边aa,后加入aba,但是遍历的时候,head[u]直接连得还是aba,所以对于起点相同的,要按字典序由大到小排序,从而使得链式前向星里的是按照从小到大,对于起点不同的,直接按字典序由小到大即可,具体见我写的cmp函数:

bool cmp(const string a, const string b)
{if(a[0]==b[0])return a>b;return a<b;// if(a<b && a[a.size()-1]>b[b.size()-1])return a>b;}

2、首先对所有输入的按照1的方法排序,从而保证遍历的时候是按照字典序遍历的,

做这个题真的对dfs,还有图的存储方式重新思考了。。。


#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>using namespace std;#define rep(i, s, e) for(int (i)=(s);(i)<(e);(i)++)
#define repe(i, s, e) for(int (i)=(s);(i)<=(e);(i)++)
#define arclr(array, a) memset(array, a, sizeof(array))
#define Debug(i) cout<<"##fuck "<<i<<endlconst int SIZE = 1000+100;
const int SLEN=28;
const int tb = 26;
int mat[tb][tb];
int father[tb],ex[tb],id[tb],od[tb],head[SIZE];
int path[SIZE],ecnt;struct Node
{int to,next;int vis;
}edge[SIZE];void addedge(int u, int v, int k)
{edge[k].to=v;edge[k].next=head[u];edge[k].vis=0;head[u]=k;
}
inline int idx(char x)
{return x-'a';
}
bool cmp(const string a, const string b)
{if(a[0]==b[0])return a>b;return a<b;// if(a<b && a[a.size()-1]>b[b.size()-1])return a>b;}
void init()
{ecnt=0;arclr(head, 0xff);arclr(path, 0xff);arclr(ex,0);arclr(id,0);arclr(od,0);rep(i,0,tb)father[i]=i;
}
string str[SIZE];int Find(int x)
{if(x!=father[x])father[x]=Find(father[x]);return father[x];
}void Union(int x, int y)
{x=Find(x);y=Find(y);if(x!=y)father[x]=y;
}int judge()
{int scnt=0;rep(i,0,tb){if(ex[i] && Find(i)==i){scnt++;if(scnt>1)return -1;}}int acnt=0,bcnt=0,pos=-1;rep(i,0,tb)if(ex[i]){if(id[i]==od[i])continue;if(id[i] == od[i]+1){acnt++;continue;}if(id[i] == od[i]-1){pos=i;bcnt++;continue;}//Debug(2);//return -1;}//Debug(3);if(!acnt&&!bcnt)return -2;//回路if(acnt==1&&bcnt==1)return pos;else return -1;
}
void euler(int u)
{for(int i=head[u];i!=-1;i=edge[i].next){if(!edge[i].vis){////cout << "caodan" << edge[i].to << endl;/edge[i].vis=1;euler(edge[i].to);path[ecnt++]=i;}}
}void output()
{for(int i=ecnt-1;i>0;i--)cout << str[path[i]] << '.';cout << str[path[0]] << endl;
}
int main()
{//freopen("poj2337.txt","r",stdin);int ncase,n,u,v;scanf("%d",&ncase);while(ncase--){init();scanf("%d",&n);rep(i,0,n)cin>>str[i],edge[i].vis=0;sort(str,str+n,cmp);////rep(i,0,n)// cout << "##**##" << str[i] << endl;//rep(i,0,n){u=idx(str[i][0]);v=idx(str[i][str[i].size()-1]);addedge(u,v,i);id[v]++;od[u]++;ex[u]=ex[v]=1;Union(u,v);}int result=judge();if(result == -1){printf("***\n");continue;}if(result==-2){euler(idx(str[0][0]));}else{euler(result);}output();}return 0;
}




这篇关于poj 2337 欧拉回路按照最小字典序输出+注意为了按最小字典序怎么处理邻接表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009604

相关文章

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Python实现自动化接收与处理手机验证码

《Python实现自动化接收与处理手机验证码》在移动互联网时代,短信验证码已成为身份验证、账号注册等环节的重要安全手段,本文将介绍如何利用Python实现验证码的自动接收,识别与转发,需要的可以参考下... 目录引言一、准备工作1.1 硬件与软件需求1.2 环境配置二、核心功能实现2.1 短信监听与获取2.

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Java使用多线程处理未知任务数的方案介绍

《Java使用多线程处理未知任务数的方案介绍》这篇文章主要为大家详细介绍了Java如何使用多线程实现处理未知任务数,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 知道任务个数,你可以定义好线程数规则,生成线程数去跑代码说明:1.虚拟线程池:使用 Executors.newVir

一文带你深入了解Python中的GeneratorExit异常处理

《一文带你深入了解Python中的GeneratorExit异常处理》GeneratorExit是Python内置的异常,当生成器或协程被强制关闭时,Python解释器会向其发送这个异常,下面我们来看... 目录GeneratorExit:协程世界的死亡通知书什么是GeneratorExit实际中的问题案例

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

电脑开机提示krpt.dll丢失怎么解决? krpt.dll文件缺失的多种解决办法

《电脑开机提示krpt.dll丢失怎么解决?krpt.dll文件缺失的多种解决办法》krpt.dll是Windows操作系统中的一个动态链接库文件,它对于系统的正常运行起着重要的作用,本文将详细介绍... 在使用 Windows 操作系统的过程中,用户有时会遇到各种错误提示,其中“找不到 krpt.dll”