pku 1094 Sorting It All Out
基本方法是拓扑排序，非常容易错。首先逐条读入关系，每读入一个关系，进行一次拓扑排序。拓扑排序可能返回三种结果，有确定唯一的顺序，无法确定唯一的顺序，有矛盾（存在环）。注意只要一但确定了唯一的顺序，立刻判定输出，即使后面的条件有矛盾也要忽略了。 例如下面数据 2 2 A<B B<A
答案是Sorted sequence determined after 1 relations: AB.
有一些需要注意的细节，在拓扑排序中，判断存在环的优先级要高于无法确定唯一的顺序的优先级。例如下面数据 4 4 A<B C<B D<B B<A 0 0
答案是Inconsistency found after 1 relations.
还有就是多组测试数据变量一定要清零，我就是因为没有清零错误了好几次。
/*
* Problem: pku1094 Sorting It All Out
* Author: Guo Jiabao
* Time: 2009.4.7 10:41
* State: Solved
* Memo: 拓扑排序
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=27;
using namespace std;
int N,M;
bool adjm[MAXN][MAXN];
int ind[MAXN];
char order[MAXN];
int topsort()
{
int k,i,j;
bool det=true;
memset(ind,0,sizeof(ind));
memset(order,0,sizeof(order));
for (i=1;i<=N;i++)
for (j=1;j<=N;j++)
if (adjm[i][j])
ind[j]++;
for (k=1;k<=N;k++)
{
i=0;
for (j=1;j<=N;j++)
if (ind[j]==0)
{
if (i==0)
i=j;
else
det=false;
}
if (i==0)
return 1;
ind[i]=-1;
order[k-1]=i+'A'-1;
for (j=1;j<=N;j++)
if (adjm[i][j])
ind[j]--;
}
if (det)
return 0;
else
return 2;
}
void solve()
{
int i,a,b,rs,sure=false;;
char C[4];
memset(adjm,0,sizeof(adjm));
for (i=1;i<=M;i++)
{
scanf("%s",&C);
a=C[0]-'A'+1;b=C[2]-'A'+1;
if (sure) continue;
adjm[a][b]=true;
rs=topsort();//0确定唯一 1矛盾 2不唯一/不完全
if (rs==0)
{
printf("Sorted sequence determined after %d relations: %s.n",i,order);
sure=true;
}
else if (rs==1)
{
printf("Inconsistency found after %d relations.n",i);
sure=true;
}
}
if (!sure)
printf("Sorted sequence cannot be determined.n");
}
int main()
{
freopen("siao.in","r",stdin);
freopen("siao.out","w",stdout);
while (scanf("%d%d",&N,&M),!(N==0 && M==0))
solve();
return 0;
}
上次修改时间 2017-02-03