pku 1270 Following Orders DFS+拓扑排序

电玩女神 2022-08-09 14:52 7阅读 0赞

题意很清晰.

可以利用dfs遍历每一组值,然后加上剪枝条件.

由于剪枝可以利用当前节点和已遍历节点的顺序关系,可以使用拓扑排序.

注意: 输入的第一行不一定是有序的,我在这里sort了一下才过.

小结: 拓扑排序用于当序列中的元素有顺序关系时求可行的序列.

\#include <iostream> \#include <algorithm> \#include <vector> using namespace std; bool edge\[26\]\[26\]; int inDegree\[26\]; char str\[50\]; char strTemp\[250\]; char ans\[27\]; int cnt; bool visited\[26\]; void dfs(int n) \{ if(n == cnt) \{ for(int i = 0; i < cnt; ++i) printf("%c", ans\[i\]); printf("/n"); return; \} for (int i = 0; i < cnt; ++i) \{ if(!visited\[str\[i\]-'a'\] && !inDegree\[str\[i\]-'a'\]) \{ visited\[str\[i\]-'a'\] = true; for(int j = 0; j < cnt; ++j) if(edge\[str\[i\]-'a'\]\[str\[j\]-'a'\]) inDegree\[str\[j\]-'a'\]--; ans\[n\] = str\[i\]; dfs(n+1); visited\[str\[i\]-'a'\] = false; for(int j = 0; j < cnt; ++j) if(edge\[str\[i\]-'a'\]\[str\[j\]-'a'\]) inDegree\[str\[j\]-'a'\]++; \} \} \} int main() \{ while(cin.getline(str, 50)) \{ cnt = (strlen(str)+1)/2; for(int i = 0; i < cnt; ++i) str\[i\] = str\[i\*2\]; str\[cnt\] = '/0'; sort(str, str+cnt); cin.getline(strTemp, 250); memset(edge, 0, sizeof(edge)); memset(visited, 0, sizeof(visited)); memset(inDegree, 0, sizeof(inDegree)); for(int i = 0; i < strlen(strTemp)+1; i+=4) \{ edge\[strTemp\[i\]-'a'\]\[strTemp\[i+2\]-'a'\] = true; inDegree\[strTemp\[i+2\]-'a'\]++; \} dfs(0); printf("/n"); \} return 0; \}

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关拓扑次序(Topological Order)

对一个[有向无环图][Link 1](Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边

深碍√TFBOYSˉ_/ 2022年09月08日 15:50/ 0 赞/ 93 阅读

相关 pku 1146 dfs

\include <iostream> using namespace std; \define MAX 52 int map\[MAX\]\[MAX\]; bool visi

我就是我/ 2022年08月13日 06:29/ 0 赞/ 185 阅读

相关 pku 1270 Following Orders DFS+拓扑排序

题意很清晰. 可以利用dfs遍历每一组值,然后加上剪枝条件. 由于剪枝可以利用当前节点和已遍历节点的顺序关系,可以使用拓扑排序. 注意: 输入的第一行不一定是有序的,我在

电玩女神/ 2022年08月09日 14:52/ 0 赞/ 8 阅读

相关 pku 1094 Sorting It All Out 拓扑排序

\include <iostream> \include <stack> using namespace std; int edge\[27\]\[27\]; //图的邻接矩阵

左手的ㄟ右手/ 2022年08月09日 13:52/ 0 赞/ 150 阅读

相关 WUST 1949 家谱树（拓扑排序+dfs）

1949: 家谱树 Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld Submitted: 7

港控/mmm°/ 2022年06月12日 04:22/ 0 赞/ 126 阅读

相关 POJ 2367 Genealogical tree（拓扑排序+dfs）

The system of Martians' blood relations is confusing enough. Actually, Martians bud when

约定不等于承诺〃/ 2022年06月11日 02:08/ 0 赞/ 134 阅读

相关 Ordering Tasks-简单的拓扑排序

[原题在这里^\_^][Link 1] 题意：通过输入m条两任务间的优先顺序，输出一个可能的任务顺序；思路；拓扑排序，就是建立一个图，每次选择入度为零的顶点，将与之

女爷i/ 2022年06月11日 00:13/ 0 赞/ 114 阅读

相关 (PAT 1146) Topological Order (拓扑排序)

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is

╰+哭是因爲堅強的太久メ/ 2022年03月19日 03:46/ 0 赞/ 141 阅读

相关 Ordering Tasks UVA 10305(拓扑排序)

John has n tasks to do. Unfortunately, the tasks are not independent and the execution o

客官°小女子只卖身不卖艺/ 2022年02月26日 02:18/ 0 赞/ 96 阅读

相关 POJ-1270-Following Orders

链接：[https://vjudge.net/problem/POJ-1270][https_vjudge.net_problem_POJ-1270] 题意：给n

浅浅的花香味﹌/ 2021年12月24日 05:05/ 0 赞/ 85 阅读