首页 > 代码库 > [洛谷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]无序字母对