首页 > 代码库 > POJ 1780 Code（欧拉通路）
POJ 1780 Code（欧拉通路）
输入n（1<=n<=6），输出长度为10^n + n -1 的字符串答案。
其中，字符串以每n个为一组，使得所有组都互不相同，且输出的字符串要求字典序最小。
显然a[01...(n-1)]和a[12...n]为相邻组，可以看做有一条边从结点a[01...(n-1)]到结点a[12...n]。
题目转化成求欧拉通路。如果以每组的值为结点，则有10^6个结点，10^7条边。会MLE。（此时其实是哈密顿通路？）
这里以每组的值为边的边权，而边的2个结点分别是前n-1位数和后n-1位数。这样点是10^5个，边是10^6。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <queue>#include <map>using namespace std;#define MP make_pair#define ll long long#define inf 0x3f3f3f3f#define maxn 100010#define maxm 1000010int ten[]={1,10,100,1000,10000,100000,1000000};struct Edge{ int v,nxt; bool vis;}e[maxm];int head[maxn],esz;void init(){esz=0;memset(head,-1,sizeof(head));}void addedge(int u,int v){ e[esz].v=v,e[esz].nxt=head[u]; e[esz].vis=false; head[u]=esz++;}int st[maxm],top;int ans[maxm];int main(){ //freopen("out","w",stdout); int n,m; while(~scanf("%d",&n) && n){ if(n==1){puts("0123456789");continue;} init(); for(int i=0;i<ten[n-1];++i){ int x = i%ten[n-2]; for(int j=9;j>=0;--j){ addedge(i,x*10+j); } } top=0; int sz=0; st[top++]=0; while(top){ int u = st[--top]; bool f=false; for(int i=head[u];i!=-1;i=e[i].nxt){ int v = e[i].v; if(e[i].vis) continue; e[i].vis = true; st[top++]=u; st[top++]=v; f=true; break; } if(f==false) ans[sz++]=u; } for(int i=0;i<n-2;++i) ans[sz++]=0; //for(int i=sz-1;i>=0;--i) printf("%d ",ans[i]); puts(""); for(int i=sz-1;i>=0;--i) printf("%d",ans[i]%10); puts(""); } return 0;}
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <queue>#include <map>using namespace std;#define MP make_pair#define ll long long#define inf 0x3f3f3f3f#define maxn 100010#define maxm 1000010int ten[]={1,10,100,1000,10000,100000,1000000};struct Edge{ int v,nxt; int w;}e[maxm];int head[maxn],esz;void init(){esz=0;memset(head,-1,sizeof(head));}void addedge(int u,int v,int w){ e[esz].v=v,e[esz].w=w,e[esz].nxt=head[u]; head[u]=esz++;}int st[maxm],top;int ans[maxm];bool vis[maxm];int main(){ //freopen("out","w",stdout); int n,m; while(~scanf("%d",&n) && n){ if(n==1){puts("0123456789");continue;} init(); for(int i=0;i<ten[n-1];++i){ int x = i%ten[n-2]; for(int j=9;j>=0;--j){ addedge(i,x*10+j,i*10+j); } } top=0; int sz=0; st[top++]=0; memset(vis,false,sizeof(vis)); vis[0]=true; while(top){ int u = st[--top]; bool f=false; for(int i=head[u];i!=-1;i=e[i].nxt){ int v = e[i].v; if(vis[e[i].w]) continue; vis[e[i].w]=true; st[top++]=u; st[top++]=v; f=true; break; } if(f==false) ans[sz++]=u; } for(int i=0;i<n-1;++i) ans[sz++]=0; //for(int i=sz-1;i>=0;--i) printf("%d ",ans[i]); puts(""); for(int i=sz-1;i>=0;--i) printf("%d",ans[i]%10); puts(""); } return 0;}
POJ 1780 Code（欧拉通路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。