首页 > 代码库 > [poj2337]求字典序最小欧拉回路
[poj2337]求字典序最小欧拉回路
注意：找出一条欧拉回路，与判定这个图能不能一笔联通。。。是不同的概念
c++奇怪的编译规则。。。生不如死啊。。。
string怎么用啊。。。cincout来救？
可以直接.length（）我也是长见识了。。。
CE怎么办啊。。。g++来救？
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#define N 2020using namespace std;string str[1010];int cnt,in[30],out[30];int ans[1010];int edgenum=0;int head[N],vet[N],pri[N],next[N],flag[N],len[N];void add(int u,int v,int w){ edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum; pri[edgenum]=w;}void dfs(int u){ int e=head[u]; while(e>0) { int v=vet[e]; if(flag[e]==0){ flag[e]=1;dfs(v);ans[cnt++]=pri[e]; } e=next[e]; }}int main(){ int cas,n;scanf("%d",&cas); while(cas--) { scanf("%d",&n); for(int i = 0;i < n;i++) cin>>str[i]; sort(str,str+n);//要输出字典序最小的解，先按照字典序排序 //for(int i=0;i<n;i++)len[i]=strlen(str[i]); edgenum=0;memset(head,0,sizeof(head)); memset(flag,0,sizeof(flag)); memset(in,0,sizeof(in));memset(out,0,sizeof(out)); int start=10000; for(int i=n-1;i>=0;i--){ int u=int(str[i][0])-‘a‘,v=int(str[i][str[i].length()-1])-‘a‘; add(u,v,i);out[u]++;in[v]++; if(u<start)start=u;if(v<start)start=v; } int cc1=0,cc2=0; for(int i=0;i<26;i++){ if(out[i]-in[i]==1){ cc1++;start=i; }else if(out[i]-in[i]==-1)cc2++;else if(out[i]-in[i]!=0)cc1=3; } if(!((cc1==0&&cc2==0)||(cc1==1&&cc2==1))){ printf("***\n");continue; } cnt=0;dfs(start); if(cnt!=n){printf("***\n");continue;} for(int i = cnt-1; i >= 0;i--) { cout<<str[ans[i]]; if(i > 0)printf("."); else printf("\n"); } }}
然而这道题可是需要把所有边一遍走掉的。
[poj2337]求字典序最小欧拉回路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。