对于N个大写字母,给定它们的一些偏序关系,要求判断出经过多少个偏序关系之后可以确定它们的排序或者存在冲突,或者所有的偏序关系用上之后依旧无法确定唯一的排序。 利用拓扑排序即可解决这个问题,但由于题目要求的是经过多少个关系之后就可以确定答案,因此每读入一个关系,就要进行一次拓扑排序,如果某一次拓扑排序之后可以确定它们的唯一排序或者发现冲突存在,则后面的直接略过。若读入所有关系之后依然无法确定唯一关系,同时也没有冲突,则输出不能确定唯一排序。若拓扑排序的过程中每次仅有一个点入度为0,则该排序是可以确定的排序,否则若多个…

2012年12月5日 0条评论 2点热度 阅读全文

给定N个球,这些球的编号分别是1-N中的某个数字,它们的重量也分别是1-N中的某个数字,任意两个球的编号和重量不相等。 给定一些类似a<b的约束,表示编号为a的球比编号为b的球轻。要求符合约束条件的各个球的重量。若答案有多种,则输出的答案必须让编号为1的球重量尽量轻,接着是编号为2的球重量尽量轻,一直到编号为N的球尽量轻。 这道题是一个拓扑排序问题,把每个编号的球看成一个点,把约束看成点之间的边,构造出一个有向图进行拓扑排序。但由于题目要求输出的答案必须是编号小的球重量尽量轻,因此如果直接拓扑排序,则得到的答…

2012年12月4日 0条评论 5点热度 阅读全文

拓扑排序入门题,此题基本正常的方法都能过,不需要判断是否存在环的情况。 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 105; struct Edge { int pos; int next; }; int n; int indeg[N]; Edge edge[N * N]; int cur; int neigh[N]; int queue…

2012年12月4日 0条评论 9点热度 阅读全文

题意:已经一个5*5的二维数组,共中0代表可通过,1代表不可。求(0,0)到(4,4)即对角线的最短路,只允许上下左右走。 分析:因为求最短路径,所以是BFS不可DFS。关键在于如何记录走过路径,路径队列每次加入新节点务必记录它的前驱节点,遍历结束后从终点依照前驱节一直找到源点求最短路径(由源点向终点可能多解,需要处理),然后用辅助栈反序。   C/C++源码: #include <iostream> #include <cstring> #include <vector&g…

2011年5月12日 0条评论 3点热度 阅读全文

Phone ListTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 10228 Accepted: 3288 Description Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these n…

2011年3月2日 0条评论 3点热度 阅读全文