标签：poj   算法   

题意：

给一个字符集和一些字符之间的小于关系，求字符集上的所有可能排列。

分析：

暴力枚举可以分为枚举子集，，枚举排列，枚举组合，这题是个简单的枚举排列，枚举过程中用小于关系剪枝即可。

代码：

//poj 1270 //sep9 #include <iostream> #include <algorithm> using namespace std; char vars[64],constraint[256],ans[64]; int g[128][128],vis[256]; int len; void dfs(int cur) { if(cur==len){ puts(ans); return ; } for(int i=0;i<len;++i){ if(vis[vars[i]]==0){ int ok=1; for(int k=0;k<cur&&ok;++k) if(g[vars[i]][ans[k]]==1) ok=0; if(ok==0) continue; ans[cur]=vars[i]; vis[vars[i]]=1; dfs(cur+1); vis[vars[i]]=0; } } } int main() { while(gets(vars)){ memset(g,0,sizeof(g)); memset(vis,0,sizeof(vis)); gets(constraint); for(int i=0;constraint[i];i+=4) g[constraint[i]][constraint[i+2]]=1; len=0; for(int i=0;vars[i];++i) if(vars[i]>='a'&&vars[i]<='z') vars[len++]=vars[i]; vars[len]='\0'; ans[len]='\0'; sort(vars,vars+len); dfs(0); puts(""); } return 0; }

poj 1270 Following Orders 枚举排列

标签：poj   算法