题目描述
给定 n 个变量和 m 个不等式。其中 n 小于等于26,变量分别用前 n 的大写英文字母表示。
不等式之间具有传递性,即若 A>B 且 B>C ,则 A>C。
请从前往后遍历每对关系,每次遍历时判断:
如果能够确定全部关系且无矛盾,则结束循环,输出确定的次序;
如果发生矛盾,则结束循环,输出有矛盾;
如果循环结束时没有发生上述两种情况,则输出无定解。
输入样例1:
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
输出样例1:
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
输入样例2:
6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0
输出样例2:
Inconsistency found after 6 relations.
思路:
裸Floyd???
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int num[N][N];
int deep[N];
int vis[N];
int mon[N];
int n,m;
void print(int ch[][N]) {//DBUG
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
cout<<ch[i][j]<<" ";
}
puts("");
}
}
int find() {
// print(num);
for(int i=1; i<=n; i++) {//裸跑Floyd
for(int j=1; j<=n; j++) {
for(int k=1; k<=n; k++) {
num[i][k]=max(num[i][k],num[i][j]+num[j][k]);
}
}
}
// print(num);
int fp=-1,tep=0;
for(int i=1; i<=n; i++) {
if(!deep[i]) fp=i,tep++;//寻找可能的最小的数,且有多少数可能最小
}
if(fp==-1) return -1;//若没有一个数度数为0则不存在最小数,不合法
if(tep>1) return 0;//若有多个数可能是最小数,则找不到答案
memset(mon,0,sizeof(mon));//初始化
mon[1]=fp;//填充最小数
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(num[mon[i]][j]==1) {//当前最大数的下一个数一定只比它大一个度
mon[i+1]=j;tep++;//找到多少个答案
break;
}
}
}
return tep==n;//当前的答案数等于总共的数 ,合法
}
int main() {
while(cin>>n>>m&&n&&m) {
bool flag=1;
int res=n;
memset(num,-0x3f,sizeof(num));//初始化
memset(deep,0,sizeof(deep));//同上
memset(vis,0,sizeof(vis));//同上
for(int i=1; i<=m; i++) {
char a,b,c;
cin>>a>>b>>c;
int k=a-'A'+1,f=c-'A'+1;
if(!vis[k]) res--,vis[k]=1;//计算前n项中还剩几个没有出现
/*
因为在前n个没出现完之前是不可能全部排出序来的
*/
if(!vis[f]) res--,vis[f]=1;
deep[f]=max(deep[f],deep[k]+1);//寻找那个数是最小数,顺便将当前较大数的深度给初始一波
num[k][f]=1;//当前两数有直接关系,可直观看出大小,但不可直观看出两数的中间数有多少,因而初始化为1
if(flag) {//如果结果已经出来就不用再计算了
int ask=find();//裸跑Floyd,顺便查询一波结果
if(num[f][k]>0) {//若当前的输入与之前的有矛盾
flag=0;
printf("Inconsistency found after %d relations.\n",i);
}
if(ask<0&&flag) {//若查询时发现矛盾
flag=0;
printf("Inconsistency found after %d relations.\n",i);
}
if(!res&&flag) {//若无矛盾且所有前n项都已经出来过了,尝试查询结果
// print(num);
if(ask>0) {//若结果合法
flag=0;
res=-1;
printf("Sorted sequence determined after %d relations: ",i);
for(int i=1; i<=n; i++) {
printf("%c",(char)mon[i]-1+'A');
}
puts(".");
}
}
}
}
if(!flag) continue;//若已经有了结果
printf("Sorted sequence cannot be determined.\n");
continue;
if(flag){//毫无用处。。。
printf("Inconsistency found after %d relations.\n",m);
}
}
return 0;
}
Floyd似乎写错了
tql!!!