http://poj.org/problem?id=1270
题目大意:
给你一串序列,然后再给你他们部分的大小,要求你输出他们从小到大的所有排列。
如a b f g 然后 a<b ,b< f 那么符合要求的有abfg abgf agbf gabf(即不能出现(a在b后面,b在f后面)
思路:
把这些字符看成点,如果存在a<b的关系,则在有向图中建立一条边 v(a,b),然后进行拓扑排序。
话说这题的输入很坑爹,那个大小关系的我还以为是4个一组。。结果被坑死了。看了discuss改了才过。。第一次写拓扑。。。。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=30; char a[MAXN]; char temp[200]; int map[MAXN][MAXN]; bool vis[MAXN]; int id[MAXN],to[MAXN],route[MAXN]; int len; void topsort(int cur) { if(cur==len) { for(int i=0;i<len;i++) printf("%c",a[ route[i] ]); printf("\n"); return; } for(int i=0;i<len;i++) { if(!vis[i] && !to[i]) { for(int j=0;j<len;j++) //与之相连的度减1 if(map[i][j]) to[j]--; vis[i]=true; route[cur]=i; topsort( cur+1 ); for(int j=0;j<len;j++) if(map[i][j]) to[j]++; vis[i]=false; } } } int main() { int kase=0; while(gets(temp)!=NULL) { if(kase) printf("\n"); kase++; memset(id,-1,sizeof(id)); memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); memset(to,0,sizeof(to)); len=0; for(int i=0;temp[i]!=‘\0‘;i++) if(temp[i] !=‘ ‘) a[len++]=temp[i]; sort(a,a+len); for(int i=0;i<len;i++) //进行编号,当然你也可以直接用STL的map id[ a[i]-‘a‘]=i; gets(temp); bool flag=0; int x; for (int i = 0; temp[i]!=‘\0‘; i++) //建立图不是i+4就好,狂WA,后看DISCUSS,跟着改了就AC了 { if (temp[i] == ‘ ‘) continue; if (!flag) x =temp[i] - ‘a‘; else { map[ id[ x ] ][ id[ temp[i]-‘a‘] ]=1; to[ id[temp[i]-‘a‘]]++; } flag = !flag; } topsort(0); } return 0; }