首页 > 代码库 > POJ 1094 Sorting It All Out
POJ 1094 Sorting It All Out
Sorting It All Out
Time Limit: 1000ms
Memory Limit: 10000KB
This problem will be judged on PKU. Original ID: 109464-bit integer IO format: %lld Java class name: Main
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sample Input
4 6A<BA<CB<CC<DB<DA<B3 2A<BB<A26 1A<Z0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD.Inconsistency found after 2 relations.Sorted sequence cannot be determined.
Source
East Central North America 2001
解题：这题说的是边读入一些关系。如果当前出现矛盾的（有环），就记录出现矛盾的是第几组关系。如果当前组已经能够确定n个字母的关系，也要记录当前是第几组。如果当前关系不唯一。那么继续了。
判关系是唯一就是时刻判断队列中的元素是不是大于1.如果大于1，说明同时有几个点入度为0.排序就不确定了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 105;18 int n,m,cnt,in[maxn],tmp[maxn],result[maxn];19 vector<int>g[maxn];20 queue<int>q;21 void init() {22 for(int i = 0; i < maxn; i++) {23 in[i] = 0;24 g[i].clear();25 }26 }27 bool Find(int x,int y) {28 for(int i = 0; i < g[x].size(); i++)29 if(g[x][i] == y) return false;30 return true;31 }32 int topSort() {33 while(!q.empty()) q.pop();34 for(int i = 0; i < n; i++)35 if(!in[i]) q.push(i);36 cnt = 0;37 bool uncertain = false;38 while(!q.empty()) {39 int u = q.front();40 if(q.size() > 1) uncertain = true;41 q.pop();42 result[cnt++] = u;43 for(int i = 0; i < g[u].size(); i++) {44 if(--in[g[u][i]] == 0) q.push(g[u][i]);45 }46 }47 if(cnt < n) return 1;48 if(uncertain) return 2;49 return 3;50 }51 int main() {52 bool ok;53 char u,v,op;54 int endPoint,flag;55 while(scanf("%d %d",&n,&m),n||m) {56 init();57 ok = false;58 getchar();59 flag = 2;60 for(int i = 1; i <= m; i++) {61 scanf("%c%c%c%*c",&u,&op,&v);62 if(ok) continue;63 if(op == ‘<‘ && Find(v-‘A‘,u-‘A‘)) {64 g[v-‘A‘].push_back(u-‘A‘);65 in[u-‘A‘]++;66 } else if(op == ‘>‘ && Find(u-‘A‘,v-‘A‘)) {67 g[u-‘A‘].push_back(v-‘A‘);68 in[v-‘A‘]++;69 }70 memcpy(tmp,in,sizeof(in));71 flag = topSort();72 if(flag != 2) {73 endPoint = i;74 ok = true;75 }76 memcpy(in,tmp,sizeof(in));77 }78 if(flag == 3) {79 printf("Sorted sequence determined after %d relations: ", endPoint);80 for(int i = cnt-1; i >= 0; i--)81 printf("%c",result[i]+‘A‘);82 puts(".");83 } else if(flag == 1) printf("Inconsistency found after %d relations.\n",endPoint);84 else puts("Sorted sequence cannot be determined.");85 }86 return 0;87 }
POJ 1094 Sorting It All Out
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。