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

相关文章

qt5cored.dll报错怎么解决? 电脑qt5cored.dll文件丢失修复技巧

《qt5cored.dll报错怎么解决?电脑qt5cored.dll文件丢失修复技巧》在进行软件安装或运行程序时,有时会遇到由于找不到qt5core.dll,无法继续执行代码,这个问题可能是由于该文... 遇到qt5cored.dll文件错误时,可能会导致基于 Qt 开发的应用程序无法正常运行或启动。这种错

电脑提示xlstat4.dll丢失怎么修复? xlstat4.dll文件丢失处理办法

《电脑提示xlstat4.dll丢失怎么修复?xlstat4.dll文件丢失处理办法》长时间使用电脑,大家多少都会遇到类似dll文件丢失的情况,不过,解决这一问题其实并不复杂,下面我们就来看看xls... 在Windows操作系统中,xlstat4.dll是一个重要的动态链接库文件,通常用于支持各种应用程序

SQL Server数据库死锁处理超详细攻略

《SQLServer数据库死锁处理超详细攻略》SQLServer作为主流数据库管理系统,在高并发场景下可能面临死锁问题,影响系统性能和稳定性,这篇文章主要给大家介绍了关于SQLServer数据库死... 目录一、引言二、查询 Sqlserver 中造成死锁的 SPID三、用内置函数查询执行信息1. sp_w

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。(1)简单定义-什么是

Golang 日志处理和正则处理的操作方法

《Golang日志处理和正则处理的操作方法》:本文主要介绍Golang日志处理和正则处理的操作方法,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考... 目录1、logx日志处理1.1、logx简介1.2、日志初始化与配置1.3、常用方法1.4、配合defer

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos

python web 开发之Flask中间件与请求处理钩子的最佳实践

《pythonweb开发之Flask中间件与请求处理钩子的最佳实践》Flask作为轻量级Web框架,提供了灵活的请求处理机制,中间件和请求钩子允许开发者在请求处理的不同阶段插入自定义逻辑,实现诸如... 目录Flask中间件与请求处理钩子完全指南1. 引言2. 请求处理生命周期概述3. 请求钩子详解3.1

Mac备忘录怎么导出/备份和云同步? Mac备忘录使用技巧

《Mac备忘录怎么导出/备份和云同步?Mac备忘录使用技巧》备忘录作为iOS里简单而又不可或缺的一个系统应用,上手容易,可以满足我们日常生活中各种记录的需求,今天我们就来看看Mac备忘录的导出、... 「备忘录」是 MAC 上的一款常用应用,它可以帮助我们捕捉灵感、记录待办事项或保存重要信息。为了便于在不同

Python处理大量Excel文件的十个技巧分享

《Python处理大量Excel文件的十个技巧分享》每天被大量Excel文件折磨的你看过来!这是一份Python程序员整理的实用技巧,不说废话,直接上干货,文章通过代码示例讲解的非常详细,需要的朋友可... 目录一、批量读取多个Excel文件二、选择性读取工作表和列三、自动调整格式和样式四、智能数据清洗五、

SpringBoot如何对密码等敏感信息进行脱敏处理

《SpringBoot如何对密码等敏感信息进行脱敏处理》这篇文章主要为大家详细介绍了SpringBoot对密码等敏感信息进行脱敏处理的几个常用方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录​1. 配置文件敏感信息脱敏​​2. 日志脱敏​​3. API响应脱敏​​4. 其他注意事项​​总结