看了discuss才真正明白这道题到底要让我们干什么,poj的discuss真心强大,通过这道题也明白了原来floyd除了找出任意两点的最短距离外,还有判断环的功能,强大!!!!
题意:给出一系列数的大小关系,然后判断这些字母能否单一排序或者有几种排序方式,还是成环
这里注意的是,当第t个语句已经决定结果了后,后面t-n句话都可以不用判断了,哪怕是t-n的语句对于前面的结果
会造成差异,也不用理会。
分析:每次加入一条边就floyd,拓扑下,判断是否构成环,或者次序单一
1 #include<stdio.h>
2 #include<string.h>
3
4 const int MAXN=30;
5 int res[MAXN];
6 int vis[MAXN];
7 int n,m;
8 int ans;
9 int cnt;
10 int cas;
11
12 int Floyd(int map[30][30])
13 {
14 int i,j,k;
15 for(k=1; k<=n; k++)
16 {
17 for(i=1; i<=n; i++)
18 {
19 for(j=1; j<=n; j++)
20 {
21 if(map[i][k] && map[k][j])
22 {
23 map[i][j]=1;
24 }
25 }
26 }
27 }
28 for(i=1; i<=n; i++)
29 {
30 if(map[i][i]==1) return 1;
31 }
32 return 0;
33 }
34
35 int Topo(int map[30][30],int degree[MAXN])
36 {
37 int i,j,p;
38 bool flag=false;
39 cas=0;
40 for(i=1; i<=n; i++)
41 {
42 p=-1;
43 cnt=flag=0;
44 if(vis[i])
45 {
46 for(j=1; j<=n; j++)
47 {
48 if(vis[j])
49 if(degree[j]==0)
50 {
51 flag=1;
52 degree[j]--;
53 res[cas++]=p=j;
54 cnt++;
55 }
56 }
57 if(cnt!=1)//存在几种排序方式
58 {
59 return 0;
60 }
61 for(j=1; j<=n; j++)
62 {
63 if(map[p][j])
64 {
65 map[p][j]=false;
66 degree[j]--;
67 }
68 }
69 }
70 }
71 return 1;
72 }
73
74 void Show()
75 {
76 int i;
77 for(i=0; i<cas; i++)
78 {
79 printf("%c",res[i]+'A'-1);
80 }
81 printf(".\n");
82 }
83
84 int main()
85 {
86 int i;
87 char str[10];
88 int map1[MAXN][MAXN];
89 int map2[MAXN][MAXN];
90 int degree1[MAXN],degree2[MAXN];
91 int a,b,flag,flag2,flag1;
92 while(scanf("%d%d",&n,&m))
93 {
94 flag=0;
95 if(n==0 && m==0) break;
96 memset(degree1,0,sizeof(degree1));
97 memset(map1,0,sizeof(map1));
98 memset(vis,0,sizeof(vis));
99 for(i=1; i<=m; i++)
100 {
101 scanf("%s",str);
102 a=str[0]-'A'+1;
103 b=str[2]-'A'+1;
104 if(!map1[a][b])
105 {
106 map1[a][b]=1;
107 vis[a]=vis[b]=1;
108 degree1[b]++;
109 }
110 if(flag) continue;//已经决定了结果,忽略后面的输入
111 memcpy(map2,map1,sizeof(map2));
112 flag1=Floyd(map2);//由于数组传递的是位置,所以函数中数组值的改变导致原数组的改变,所以复制一个数组传递
113 if(flag1==1)
114 {
115 printf("Inconsistency found after %d relations.\n",i);
116 flag=1;
117 }
118 memcpy(map2,map1,sizeof(map1));
119 memcpy(degree2,degree1,sizeof(degree2));
120 flag2=Topo(map2,degree2);
121 if(flag2 && cas==n)
122 {
123 printf("Sorted sequence determined after %d relations: ",i);
124 flag=1;
125 Show();
126 }
127 }
128 if(!flag) printf("Sorted sequence cannot be determined.\n");
129
130 }
131 return 0;
132 }