首页 > 代码库 > [洛谷P1341]无序字母对
[洛谷P1341]无序字母对
题目大意:见原题目描述,说的很清楚。
算法:图论、欧拉路径
思路:题目数据中没有重复条件,因此成功得到解有两种可能。①n个点,n条路径,形成欧拉回路(没有奇数点);②n+1个点,n条路径,形成欧拉路径(只有2个奇数点)。因此先判断是否有解,如果有就用dfs搜欧拉路径(回路)即可。
我这里给每个字母都进行了编号,使用时可以编号和原字母互相转换。
C++ Code:
#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#define N 3000using namespace std;int n,m=0;bool b[N][N];int ctoi[N],hasR[N],odd1,odd2,odds;char itoc[N],s[3],inp[N],ans[N];void dfs(int now,int p){ ans[p]=itoc[now]; if(p>n){ printf("%s",ans+1); exit(0); } for(int i=1;i<=m;i++) if(b[now][ctoi[inp[i]]]){ b[now][ctoi[inp[i]]]=b[ctoi[inp[i]]][now]=false; dfs(ctoi[inp[i]],p+1); b[now][ctoi[inp[i]]]=b[ctoi[inp[i]]][now]=true; } ans[p]=‘\0‘;}int main(){ scanf("%d",&n); memset(ctoi,0,sizeof(ctoi)); memset(itoc,0,sizeof itoc); memset(hasR,0,sizeof hasR); memset(b,0,sizeof b); for(int i=1;i<=n;i++){//读入、处理,将每个字母编号 scanf("%s",s); if(!ctoi[s[0]]){ m++; ctoi[s[0]]=m; itoc[m]=s[0]; inp[m]=s[0]; } if(!ctoi[s[1]]){ m++; ctoi[s[1]]=m; itoc[m]=s[1]; inp[m]=s[1]; } b[ctoi[s[1]]][ctoi[s[0]]]=b[ctoi[s[0]]][ctoi[s[1]]]=true; hasR[ctoi[s[0]]]++; hasR[ctoi[s[1]]]++; } sort(inp+1,inp+m+1); odds=0; for(int i=1;i<=m;i++) if(hasR[i]%2){ odds++; if(odds==1)odd1=i;else if(odds==2)odd2=i;else{ printf("No Solution"); return 0; } } if(odds!=0&&odds!=2){ printf("No Solution"); return 0; } int start; if(odds==2){ if(itoc[odd1]<itoc[odd2])start=odd1;else start=odd2; } else start=ctoi[inp[1]]; memset(ans,‘\0‘,sizeof ans); dfs(start,1); return 0;}
[洛谷P1341]无序字母对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。