首页 > 代码库 > poj1270拓扑排序
poj1270拓扑排序
题意：给定一些大小关系，把关系从大到小排序，如果有多种相同关系就按字典序排序。例如 x < y && x < z 则满足关系的有xyz 和 xzy 。
思路：我们可以把每组大小关系建一条有向边，这样就形成了一个有向图，再对有向图进行拓扑，得到的结果即满足。但是拓扑出来的是一组可行解，而题意是要输出所有可行解，刚好可以想到递归求拓扑时可以回溯；那样就可以把所有的可行解输出。不过要把所有的变量排序。
代码：
#pragma warning (disable: 4786)#include<cstdio>#include<cstring>#include<algorithm>#include<map>const int maxn = 200;char var[maxn];char ans[maxn];char st[maxn];int map[maxn][maxn];int n;int indeg[maxn];std::map<char,int>hash;void toposort(int k) //拓扑回溯{ if(k == n) { ans[n] = ‘\0‘; printf("%s\n",ans); return ; } for(int i=0; i< n; i++) { int j; if(indeg[i] == 0) { indeg[i] -- ; ans[k] = st[i]; for(j =0;j < n;j++) { if(map[i][j]) indeg[j] --; } toposort(k+1); indeg[i] ++; for(j=0;j<n;j++) if(map[i][j]) indeg[j] ++; } }}void init(){ n = 0; memset(indeg,0,sizeof(indeg)); memset(map,0,sizeof(map));}void work(){ char c[3]; int i; int l = strlen(var),k =0; init(); for( i =0;i<l;i++) { if(var[i] >= ‘a‘ && var[i] <= ‘z‘) st[n++] = var[i]; } std::sort(st,st+n); for(i=0;i<n;i++) { hash[st[i]] = i; } gets(var); l = strlen(var); for( i=0; i<l; i++) { if(var[i] >= ‘a‘ && var[i] <= ‘z‘) { c[k%2] = var[i]; if(k % 2 == 1) { map[hash[c[0]]][hash[c[1]]] = 1; indeg[hash[c[1]]] ++; } k++; } } toposort(0); printf("\n");}int main(){ while(gets(var)) { work(); } return 0;}/*a b f ga b b fv w x y zv y x v z v w v */
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。