[ACM_模拟] POJ 1094 Sorting It All Out (拓扑排序+Floyd算法 判断关系是否矛盾或统一)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

[ACM_模拟] POJ 1094 Sorting It All Out (拓扑排序+Floyd算法 判断关系是否矛盾或统一)

简介:


Description

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. 

Sample Input

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

 
题目大意:给你一些大写字母间的大小排序关系,判断以下3中情况:1 能唯一确定它们的排列顺序,2 所给关系是矛盾的,3 到最后也不能确定它们之间的关系。

解题思路:a、出现矛盾也就是在比较大小关系的过程中出现环,可以通过Floyd算法由邻接矩阵求出可达矩阵,再判断是否存在map[i][i]=1的情况

              b、如果没有环且每个点的出度+入度==n-1,则表明字母之间两两关系确定,构成唯一的一个序列,存在答案,否则不存在。

              c、当答案存在时,利用拓扑排序确定各点顺序。

相关知识:a、Floyd算法:Floyd-Warshall算法,简称Floyd算法,用于求解任意两点间的最短距离,时间复杂度为O(n^3)。其一般形式为:

复制代码
1 void Floyd(){
2      for(int k=1;k<=n;k++)
3          for(int i=1;i<=n;i++)
4              for(int j=1;j<=n;j++)
5                  if(dist[i][k]+dist[k][j]<dist[i][j])
6                      dist[i][j]=dist[i][k]+dist[k][j];
7 }
复制代码

在调用它之前只需做一些简单的初始化:dist[i][i]=0,其他dist为INF。注意这里存在一个潜在问题:当INF定义太大,加法dist[i][k]+dist[k][j]可能会溢出!但如果INF太小,可能会是长度为INF的边真的变成最短路的一部分。因此INF不能太大也不能太小,要先估算一下!如果坚持认为不应该允许INF和其他值相加,就需要把代码改成:

复制代码
1 void Floyd(){
2      for(int k=1;k<=n;k++)
3          for(int i=1;i<=n;i++)
4              for(int j=1;j<=n;j++)
5                  if(dist[i][k]<INF && dist[k][j]<INF && dist[i][k]+dist[k][j]<dist[i][j])
6                      dist[i][j]=dist[i][k]+dist[k][j];
7 }
复制代码

此外本题用到了有向图的传递闭包:在有向图中,有时不必关心路径的长度,而只关心两点是否有通路,则可以用1、0分别表示“连通”和“不连通”。这样除了预处理需要做少许修改外,主算法只需:

复制代码
1 void Floyd(){
2      for(int k=1;k<=n;k++)
3          for(int i=1;i<=n;i++)
4              for(int j=1;j<=n;j++)
5                  if(dist[i][k] && dist[k][j])
6                      dist[i][j]=1;
7 }
复制代码

b、拓扑排序:拓扑排序是对有向无环图(DAG图)的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环,则无法表示两个顶点的先后顺序。

                   在现实生活中,也会有不少应用例子,比如学校课程布置图,要先修完一些基础课,才可以继续修专业课。

                   有向图可以拓扑排序的条件是:图中没有环。

                   具体方法:
                   ⑴ 从图中选择一个入度为0的点加入拓扑序列。
                   ⑵ 从图中删除该结点以及它的所有出边(即与之相邻点入度减1)。

                   反复执行这两个步骤,直到所有结点都已经进入拓扑序列。

相关链接:Folyd算法详解 http://www.cppblog.com/wing/archive/2011/03/10/141511.html

      如何理解拓扑排序算法 http://www.cnblogs.com/shanyou/archive/2006/11/16/562861.html

      拓扑排序-离散数学-详解 http://sjjg.js.zwu.edu.cn/SFXX/tu/tu5.6.1.html

AC代码

复制代码
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #include<string>
 5 #include<stack>
 6 using namespace std;
 7 
 8 #define maxn 30
 9 int n,m;
10 bool map[maxn][maxn],visit[maxn];
11 int indegree[maxn],outdegree[maxn];
12 char str[maxn],ch[maxn];
13 
14 bool Floyd(){
15     for(int i=0;i<n;i++)//Floyd对邻接矩阵的运算求可达矩阵
16         for(int j=0;j<n;j++)
17             for(int k=0;k<n;k++)
18                 if(map[j][i] && map[i][k])
19                     map[j][k]=1;
20     for(int l=0;l<n;l++)//判断是否成环
21         if(map[l][l])
22             return 0;
23     return 1;
24 }//Floyd算法对0-1邻接矩阵判断是否有环:map[i][i]=1
25 
26 bool only_sure(){
27     memset(indegree,0,sizeof(indegree));
28     memset(outdegree,0,sizeof(outdegree));
29     for(int i=0;i<n;i++)//计算出度和入度
30         for(int j=0;j<n;j++)
31             if(map[i][j])
32                 indegree[j]++,outdegree[i]++;
33     for(int k=0;k<n;k++)//所有点出度入度之和均为n-1则说明所有关系确定
34         if(indegree[k]+outdegree[k]!=n-1)
35             return 0;
36     return 1;
37 }
38 
39 //拓扑排序:从图中选择一个入度为0的点加入拓扑序列
40 //         从图中删除该结点以及它的所有出边(即与之相邻点入度减1)
41 void toplogical_sort(){
42     stack<int> Q;
43     int id=0;
44     for(int i=0;i<n;i++)
45         if(indegree[i]==0){
46             Q.push(i);
47             break;
48         }
49     memset(visit,0,sizeof(visit));
50     while(!Q.empty()){
51         int cur=Q.top();Q.pop();
52         visit[cur]=true;
53         str[id++]=cur+'A';
54         for(int j=0;j<n;j++){
55             if(!visit[j] && map[cur][j])indegree[j]--;//将所有子节点的入度-1
56             if(!visit[j] && indegree[j]==0)Q.push(j);
57         }    
58     }
59     str[id]='\0';
60 }
61 
62 int main(){
63     while(cin>>n>>m){
64         if(n==0 && m==0)break;
65         memset(map,0,sizeof(map));
66         int flag1=0;//标记矛盾出现时的步数
67         int flag2=0;//标记关系确认时的步数
68         for(int i=1;i<=m;i++){//边输入边检测
69             cin>>ch;
70             map[ch[0]-'A'][ch[2]-'A']=1;
71             if(flag1 ||flag2)continue;
72             else if(!Floyd())flag1=i;
73             else if(only_sure()){
74                 toplogical_sort ();
75                 flag2=i;
76             }
77         }
78         if (flag1) printf("Inconsistency found after %d relations.\n",flag1);
79         else if (flag2) printf("Sorted sequence determined after %d relations: %s.\n",flag2,str);
80         else printf("Sorted sequence cannot be determined.\n");
81     }return 0;
82 }
复制代码

 




本文转自beautifulzzzz博客园博客,原文链接:http://www.cnblogs.com/zjutlitao/p/3554256.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: