Floyd倍增(求传递闭包) - Sorting It All Out - POJ 1094

Floyd/倍增(求传递闭包) - Sorting It All Out - POJ 1094

给定 n 个变量和 m 个不等式。其中 n 小于等于26，变量分别用前 n 的大写英文字母表示。

不等式之间具有传递性，即若 A>B 且 B>C ，则 A>C。

请从前往后遍历每对关系，每次遍历时判断：

如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序； 如果发生矛盾，则结束循环，输出有矛盾； 如果循环结束时没有发生上述两种情况，则输出无定解。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数n和m。

接下来m行，每行包含一个不等式，不等式全部为小于关系。

当输入一行0 0时，表示输入终止。

输出格式

每组数据输出一个占一行的结果。

结果可能为下列三种之一：

如果可以确定两两之间的关系，则输出

Sorted sequence determined after t relations: yyy...y.

,其中’t’指迭代次数，'yyy…y’是指升序排列的所有变量。

如果有矛盾，则输出：

Inconsistency found after t relations.

，其中’t’指迭代次数。

如果没有矛盾，且不能确定两两之间的关系，则输出

Sorted sequence cannot be determined.

数据范围

$2\le n\le 26，变量只可能为大写字母AZ。$

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.

---

分析：

$由于小于号具有传递性，本题本质上是求一个传递闭包。$

$对于给定条件，我们通过邻接矩阵g来存储两个变量之间的大小关系。$

$若g[i][j]=1，则表示i<j，否则表示i与j之间无关系。$

$由于要输出在第几步得出结论，故我们每输入一个已知条件，就要更新一遍整个邻接矩阵。$

$也就是每增加一条边，就要更新一次图中所有点之间的连通性。$

$假设我们新增已知条件A<B，那么就要将已知的小于A的所有点i和B建立连通关系，标记g[i][B]=1。$

$同理，还要讲已知的大于B所有点j和A建立连通关系，标记g[A][j]=1。$

$需要解决的问题：$

$①、建立新的连通关系：$

$假设新的已知条件:i<j，则先标记g[i][j]=1。$

$接着可以全图跑一遍floyd，对于任意三点i,j,k，若d[i][k]=1且d[k][j]=1，则更新d[i][j]=1，$

$时间复杂度为O(n^3)。$

$也可以两重循环，将所有小于i的点a与j建立连通关系，即若g[a][i]=1，则更新g[a][j]=1。$

$同理，将所有大于j的点b与i建立连通关系，即若g[j][b]=1，则更新g[i][b]=1。$

$②、判断是否能够得出结论：$

$Ⅰ、矛盾：若i<j且j<i，我们能够得出矛盾，即d[i][j]=d[j][i]=1，矛盾。$

$我们发现，上述矛盾条件等价于d[i][i]=1，因此可在O(n)的时间下判断是否矛盾。$

$Ⅱ、暂时还不确定结论：若存在d[i][j]=0且d[j][i]=0，即i和j之间的大小关系不确定，则说明结论未定。$

$Ⅲ、可确定结论：直接判断较麻烦。但是，若不满足情况Ⅰ和Ⅱ，则说明能确定结论。$

$③、如何确定在第几个已知条件能够得出结论或者矛盾。$

$用整型变量type来标记，0表示可确定结论，1表示矛盾，2表示暂不确定。$

$每次读入新的条件，若type=2，则建立连通关系，接着根据②判断结论是否能够确定。$

$判断完后更新type，若type\ne 2，则记录当前的条件编号step=i。$

$④、若可确定结论，如何从小到大输出所有的变量。$

$由于n\le 26，我们可以两重循环，每次找到最小的一个变量返回，并标记。$

Floyd-O(mn³)：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=27; int n,m; bool g[N][N],d[N][N]; bool st[N]; //标记输出最小字母 void floyd() { memcpy(d,g,sizeof d); for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]|=d[i][k]&d[k][j]; } int check() { for(int i=0;i<n;i++) if(d[i][i]) //矛盾 return 1; for(int i=0;i<n;i++) for(int j=0;j<i;j++) if(!d[i][j] && !d[j][i]) //不确定 return 2; return 0; } char get_min() { for(int i=0;i<n;i++) if(!st[i]) { bool flag=true; //判断有没有比i更小的 for(int j=0;j<n;j++) if(!st[j] && d[j][i]) { flag=false; break; } if(flag) { st[i]=true; return 'A'+i; } } } int main() { while(cin>>n>>m,n||m) { memset(g,0,sizeof g); char str[5]; int step=0,type=2; for(int i=1;i<=m;i++) { cin>>str; int a=str[0]-'A',b=str[2]-'A'; if(type==2) { g[a][b]=1; floyd(); type=check(); if(type!=2) step=i; } } if(!type) { memset(st,0,sizeof st); printf("Sorted sequence determined after %d relations: ",step); for(int i=0;i<n;i++) printf("%c",get_min()); puts("."); } else if(type==1) printf("Inconsistency found after %d relations.\n",step); else if(type==2) puts("Sorted sequence cannot be determined."); } return 0; }

倍增算法-O(mn²)：

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=27; int n,m; bool d[N][N]; bool st[N]; //标记输出最小字母 void add(int a,int b) { d[a][b]=1; for(int i=0;i<n;i++) { if(d[i][a]) d[i][b]=1; if(d[b][i]) d[a][i]=1; for(int j=0;j<n;j++) if(d[i][a]&&d[b][j]) d[i][j]=1; } } int check() { for(int i=0;i<n;i++) if(d[i][i]) //矛盾 return 1; for(int i=0;i<n;i++) for(int j=0;j<i;j++) if(!d[i][j] && !d[j][i]) //不确定 return 2; return 0; } char get_min() { for(int i=0;i<n;i++) if(!st[i]) { bool flag=true; //判断有没有比i更小的 for(int j=0;j<n;j++) if(!st[j] && d[j][i]) { flag=false; break; } if(flag) { st[i]=true; return 'A'+i; } } } int main() { while(cin>>n>>m,n||m) { memset(d,0,sizeof d); char str[5]; int step=0,type=2; for(int i=1;i<=m;i++) { cin>>str; int a=str[0]-'A',b=str[2]-'A'; if(type==2) { add(a,b); type=check(); if(type!=2) step=i; } } if(!type) { memset(st,0,sizeof st); printf("Sorted sequence determined after %d relations: ",step); for(int i=0;i<n;i++) printf("%c",get_min()); puts("."); } else if(type==1) printf("Inconsistency found after %d relations.\n",step); else if(type==2) puts("Sorted sequence cannot be determined."); } return 0; }