Floyd算法的变化应用：
大家应该都知道Floyd在图中的任意两点最短路径的算法中的应用吧。现在我们来看一个Floyd在其它方面的应用……
题目：
Sorting It All Out（zju1060）
问题描述：
若变量 A, B, C, D已排好序,意味着: A < B, B < C,C < D. 本问题中,将给出一组变量间的小于关系，请你判断它们是否能确定一个排好的序列。
输入：
4
A<B
A<C
B<C
C<D
B<D
A<B
3 2 //又一ＴＥＳＴ
A<B
B<A
26 1
A<Z
0 0 //00结束
输出：
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
说明：
第一组：前4个关系式就能确定序列
第二组：前两个关系式中出现矛盾
第三组：不能确定
问题分析：
★ n个元素要是能确定一个全序，任意两个元素间必能比较大小，这样关系总数应该有n-1 + n-2 + n-3 + …+1 = n*(n-1)/2 个。
★ 当关系式能产生n*(n-1)/2 个关系时，序列可确定。(直接排序)
★ 由于关系只有小于，我们可以用邻接矩阵来表示元素之间的小于关系。
★ 当d[i][j]=d[j][i]且d[i][j]=1时，(就是不能A<B又B<A)出现矛盾
★ 
★ 当关系式不能产生n*(n-1)/2 个关系，也未出现矛盾，则序列不能确定。
★ 现在可以确定对图的操作：由传递性把关系补充完全。然后判断矛盾；若无矛盾，统计邻接矩阵内1的个数。
★ 使用算法： Floyd算法
//计算传递性
for(x=0;x<n;x++)
for(y=0;y<n;y++)
for(z=0;z<n;z++)
if(relation[y][x]&&relation[x][z])
relation[y][z]=1; //不计算最短路径
源程序如下：
#include <iostream>
#include <algorithm>
using namespace std;
int relation[26][26]; //关系邻接矩阵
char data[26]; //存储N个字母
int change(char a) //把大写字母变成矩阵中的序号
{
return a-65;
}
void Sort(int n) //成功时对字母的排序输出
{ int i;
for( i=0;i<n;i++)
data[i]='A'+i;
sort(data,data+n);
for(i=0;i<n;i++)
cout<<data[i];
cout<<endl;
}
int main()
{
int n,m,flag,F,x,y,z,i,count,T,U;
char tx,tt,ty;
cin>>n>>m;
do //整个大循环，遇00时结束程序
{
T=U=0;
if(n==0&&m==0)
break;
memset(relation,0,sizeof(relation));
flag=F=0;
for(i=0;i<m;i++) //m个关系，每读入一对关系都要操作，因为要计算所用的关系数
{
cin>>tx>>tt>>ty;
if(flag||F) //flag 为冲突标志 ;F为已经满足的标志
continue;
relation[change(tx)][change(ty)]=1;
for(x=0;x<n;x++) //Floyd计算传递性
for(y=0;y<n;y++)
for(z=0;z<n;z++)
if(relation[y][x]&&relation[x][z])
relation[y][z]=1;
count=0;
for(x=0;x<n;x++)
{ for(y=0;y<n;y++)
{
if(relation[x][y]&&relation[y][x]) //检验冲突
{
U=i+1; //记录检验到冲突时已经检验的关系数
flag=1; break;
}
else if(relation[x][y]||relation[x][y])
count++;
} //for
if(flag) break;
} //for
if(flag) continue;
if(count==n*(n-1)/2)
{
T=i+1; //记录满足条件时的检验的关系数
F=1;
}
} //for
if(U)
{
cout<<"Inconsistency found after "
<<U<<" relations.\n";
goto next; //进入大循环
}
else if(count!=n*(n-1)/2)
{
cout<<"Sorted sequence cannot be determined.\n";
goto next;
}
cout<<"Sorted sequence determined after "
<<T<<" relations: ";
Sort(n);
next: cin>>n>>m;
}while(1);
}
评论