题目链接: http://poj.org/problem?id=1270
题目大意: 第一行给出字符串(小写字母),表示出现的字符类型
第二行是约束关系,a1 b1 a2 b2 a3 b3.....ai bi,表示ai必须在bi前面
按照字典序输出所有满足约束条件的序列
如:
y z x
x z
xyz
xzy
yxz
解题思路: 题目要求字典序输出,先把给出第一行字符串排序
所有的约束条件变成有向图的边,x z表示顶点x到顶点z的边
序列的情况是否跟有向图有冲突,不冲突则正确,否则舍去
用深搜把所有满足的情况都搜索一边
每次找到入度为0的顶点就开始进入下一层,存入a[len],并且把与这个顶点相连的点的入度都减1
直到搜索到的层数len等于字符串的长度,就输出a[ ]
也就是在搜索过程中融合拓扑排序的思想,直到不存在入度为0的顶点为止
剪枝: 把字符串转换成数字可以大大提高效率,如y z x 转换为 1 2 0
代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdlib.h> #include <algorithm> using namespace std; #define MAX 200 char ch1[MAX],ch2[MAX],ch3[MAX]; int n,m,zm[MAX],edge[MAX][MAX],to[MAX],visit[MAX],a[MAX]; bool comp(char a,char b) { return a<b; } void DFS(int len) { int i,j; if(len==n) //层数等于字符串长度则输出 { for(i=0;i<n;i++) { printf("%c",ch1[a[i]]); } printf("\n"); return ; } for(i=0;i<n;i++) { if(!visit[i]&&!to[i]) { for(j=0;j<n;j++) //把与这个顶点相连的点入度减1 { if(edge[i][j]==1) { to[j]--; } } visit[i]=1; //标记此点访问过 a[len]=i; DFS(len+1); for(j=0;j<n;j++) //还原现场: 把减掉的入度加回去 { if(edge[i][j]==1) { to[j]++; } } visit[i]=0; //还原现场 } } return ; } int main() { int i,k,pd=0; while(gets(ch3)) { if(pd==0) pd=1; else printf("\n"); //测试用例之间输出空行 gets(ch2); memset(zm,-1,sizeof(zm)); memset(edge,-1,sizeof(edge)); memset(to,0,sizeof(to)); memset(visit,0,sizeof(visit)); for(i=0,n=0;ch3[i]!='\0';i++) //去除空格 { if(ch3[i]==' ') continue; ch1[n++]=ch3[i]; } sort(ch1,ch1+n,comp); //排序 for(i=0;i<n;i++) //字符串1处理,把字母转化成0到n-1的边 { zm[ch1[i]-'a']=i; } for(i=0,k=0;ch2[i]!='\0';i+=4) //字符串2处理,构建有向图 { edge[zm[ch2[i]-'a']][zm[ch2[i+2]-'a']]=1; to[zm[ch2[i+2]-'a']]++; //顶点入度+1 } DFS(0); // printf("\n"); 这样输出空行poj可以过,UVA会WA } return 0; }
方法2: 利用STL库里面的next_permutation()函数,把所有的字符串全排列都找出
把符合情况的字符串输出,不符合的舍去
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdlib.h> #include <algorithm> using namespace std; #define MAX 200 char ch1[MAX],ch2[MAX],ch3[MAX]; int n,m,zm[MAX],edge[MAX][MAX],to[MAX],visit[MAX],a[MAX]; bool comp(char a,char b) { return a<b; } int Topsort(char ch[]) { int i,j; for(i=n-1;i>0;i--) { for(j=i-1;j>=0;j--) { if(edge[zm[ch[i]-'a']][zm[ch[j]-'a']]==1) return 0; } } return 1; } int main() { int i,k,pd=0; while(gets(ch3)) { if(pd==0) pd=1; else printf("\n"); gets(ch2); memset(zm,-1,sizeof(zm)); memset(edge,-1,sizeof(edge)); memset(to,0,sizeof(to)); memset(visit,0,sizeof(visit)); for(i=0,n=0;ch3[i]!='\0';i++) //去空格 { if(ch3[i]==' ') continue; ch1[n++]=ch3[i]; } ch1[n]='\0'; sort(ch1,ch1+n,comp); //排序 for(i=0;i<n;i++) //字符串1处理,把字母转化成0到n-1的边 { zm[ch1[i]-'a']=i; } for(i=0,k=0;ch2[i]!='\0';i+=4) //字符串2处理,构建有向图 { edge[zm[ch2[i]-'a']][zm[ch2[i+2]-'a']]=1; to[zm[ch2[i+2]-'a']]++; } if(Topsort(ch1)) //符合限制条件则输出 printf("%s\n",ch1); while(next_permutation(ch1,ch1+n)) { if(Topsort(ch1)) //符合限制条件则输出 printf("%s\n",ch1); } // printf("\n"); } return 0; }
注: 原创文章,转载请注明出处