本文主要是介绍zoj 1919 poj 2337 Catenyms（欧拉路径求解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
zoj 1919 poj 2337 Catenyms
前一个单词的尾字母与后一个单词的第一个字母相同
输出字典序最小的序列
用向量数组e[i]来存储以i开头的字符串 由于要是按字典序输出 所以需要讲字符串排序
f[i][j]数组表示 以第i个字母开头的第j个单词有没有被选取
level记录递归的层数 到达n之后 所有单词被选取 结束
yes标记有木有找到 找到了之后 递归 循环都结束
其他的基本都是模版的东西 并查集判断是不是连通
判断能不能形成欧拉图 根据度数情况选取dfs的起点
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 1010
#define INF 0x7fffffff
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;int n;
int rd[30],cd[30];
int par[30];
vector<string> e[30],ans;
int f[30][1010],w[30][1010];
int yes,level;
int num;struct edge
{int u,v;
};
edge ed[1000100];void init()
{for(int i=0;i<26;i++)par[i]=-1;
}int Find(int x)
{int s;for(s=x;par[s]>=0;s=par[s]);while(s!=x){int tmp=par[x];par[x]=s;x=tmp;}return s;
}void Union(int R1,int R2)
{int r1=Find(R1),r2=Find(R2);int tmp=par[r1]+par[r2];if(par[r1]>par[r2]){par[r1]=r2;par[r2]=tmp;}else{par[r2]=r1;par[r1]=tmp;}
}bool conn()
{
// init();for(int i=0;i<num;i++){int u=ed[i].u,v=ed[i].v;if(u!=v&&Find(u)!=Find(v))Union(u,v);}int fir=-1;for(int i=0;i<26;i++){if(rd[i]+cd[i]==0)continue;if(fir==-1) fir=i;else if(Find(i)!=Find(fir))return 0;}return 1;
}void dfs(int x)
{
// cout<<"666"<<endl;if(level==n) {yes=1; return; }int i;for(i=cd[x]-1;i>=0;i--)//从小到大寻找可行路径{int y=w[x][i];if(!f[x][i])//以a开头的第i个串 没有被用过{level++; f[x][i]=1;dfs(y);level--; f[x][i]=0;}if(yes) break;}if(yes) ans.push_back(e[x][i]);
}int main()
{
//freopen("ceshi.txt","r",stdin);int tc;scanf("%d",&tc);while(tc--){init();MEM(rd,0); MEM(cd,0); MEM(f,0); MEM(w,0);for(int i=0;i<30;i++)e[i].clear();ans.clear();num=0;scanf("%d",&n);getchar();char s[40];for(int i=0;i<n;i++){scanf("%s",s);string str=s;
// cin>>str;int u=str[0]-'a';e[u].push_back(str);cd[u]++;}for(int i=0;i<26;i++){sort(e[i].begin(),e[i].end());reverse(e[i].begin(),e[i].end());}for(int i=0;i<26;i++){
// cout<<"cd "<<cd[i]<<endl;for(int j=0;j<cd[i];j++){int len=e[i][j].length();int v=e[i][j][len-1]-'a';rd[v]++;int u=e[i][j][0]-'a';
// Union(u,v);ed[num].u=u; ed[num].v=v;num++;w[i][j]=v;//以i开头 从大到小排序之后 第j个串的尾字母是v}}
// cout<<"666"<<endl;int flag=1;int start=-1;int cr=0,rc=0;for(int i=0;i<26;i++){if(rd[i]-cd[i]>=2||cd[i]-rd[i]>=2){flag=0; break;}if(rd[i]-cd[i]==1){rc++;if(rc>1){flag=0; break;}}if(cd[i]-rd[i]==1){cr++;start=i;if(cr>1){flag=0; break;}}}if(rc!=cr) flag=0;if(!conn()) flag=0;yes=0; level=0;if(!flag)puts("***");else{if(start>=0){dfs(start);
// reverse(ans.begin(),ans.end());}else{for(int i=0;i<26&&!yes;i++){level=0;if(cd[i])dfs(i);}}reverse(ans.begin(),ans.end());for(int i=0;i<n-1;i++)cout<<ans[i]<<".";cout<<ans[n-1]<<endl;}}return 0;
}
这篇关于zoj 1919 poj 2337 Catenyms（欧拉路径求解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
