思路
弗洛伊德传递闭包(呃……很显然的嘛)
C++ 代码
#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
char c;bool f=0;
while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
x=c^48;
while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
if(f)x=-x;
}
const int maxn=27;
int n,m,f[maxn][maxn],vis[maxn];
//f是闭包关系,vis是统计大于了几个数
char a[maxn];
//a是最后输出数组
int main()
{
freopen("in.txt","r",stdin);
while(2333)
{
rd(n),rd(m);
if(!n)re 0;
memset(f,0,sizeof f);
memset(vis,0,sizeof vis);
//每次刷新的好习惯
char s[45];
int flag=0,flag1=1,flag2=0;
//flag是统计有现有多少关系(因为传递闭包,所以我们可以得出所有关系数)
//仿佛不是很严谨~
//不过我们可知正确答案的关系数(大于数)是唯一的:1,2,3,4,5……n-1;
//其他非正确答案(矛盾导致)会被我们排除
inc(i,1,m)
{
scanf("%s",s);
int x=s[0]-'A'+1,y=s[2]-'A'+1;
//只有出现的字母与关系才赋值
f[x][y]=1;
f[x][x]=f[y][y]=1;
//闭包传递
inc(j,1,26)inc(k,1,26)
f[j][k]|=f[j][x]&f[y][k];
flag=0,flag1=1;
//检验
inc(j,1,26)inc(k,1,26)
{
if(j!=k&&f[j][k]&f[k][j])flag1=0;
if(f[j][k]&(!f[k][j]))++flag;
}
if(!flag1)//出现矛盾
{
printf("Inconsistency found after %d relations.\n",i);
flag2=1;
break;
}
if(flag>=(n-1)*n/2)//关系数符合
{
printf("Sorted sequence determined after %d relations:",i);
flag2=1;
inc(j,1,26)inc(k,1,26)
if(f[j][k])++vis[k];
inc(k,1,26)
a[vis[k]]=k+'A'-1;
inc(k,1,n)
printf("%c ",a[k]);
printf("\n");
break;
}
}
if(!flag2)printf("Sorted sequence cannot be determined.\n");
}
re 0;
}
吐槽
这道题的数据格外的水
每次枚举到n就ac了
water code
#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
char c;bool f=0;
while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
x=c^48;
while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
if(f)x=-x;
}
const int maxn=27;
int n,m,f[maxn][maxn],vis[maxn];
char a[maxn];
inline void Floyd()
{
inc(k,1,n)
inc(i,1,n)
inc(j,1,n)
f[i][j]|=(f[i][k]&f[k][j]);
}
int main()
{
// freopen("in.txt","r",stdin);
while(2333)
{
rd(n),rd(m);
if(!n)re 0;
memset(f,0,sizeof f);
memset(vis,0,sizeof vis);
char s[45];
int flag=0,flag1=1,flag2=0;
inc(i,1,m)
{
scanf("%s",s);
int x=s[0]-'A'+1,y=s[2]-'A'+1;
f[x][y]=1;
f[x][x]=f[y][y]=1;
inc(j,1,n)inc(k,1,n)
f[j][k]|=f[j][x]&f[y][k];
flag=1,flag1=1;
inc(j,1,n)inc(k,1,n)
{
if(j!=k&&f[j][k]&f[k][j])flag1=0;
if(!f[j][k]&(!f[k][j]))flag=0;//判断是否有未确定关系???
}
if(!flag1)
{
printf("Inconsistency found after %d relations.\n",i);
flag2=1;
break;
}
if(flag)
{
printf("Sorted sequence determined after %d relations: ",i);
flag2=1;
inc(j,1,n)inc(k,1,n)
if(f[j][k])++vis[k];
inc(k,1,n)
a[vis[k]]=k+'A'-1;
inc(k,1,n)
printf("%c",a[k]);
printf(".\n");
break;
}
}
if(!flag2)printf("Sorted sequence cannot be determined.\n");
}
re 0;
}