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 1000010

int 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;

}

巴特西

POJ 1780 Code（有向图的欧拉通路）

最新文章

热门文章