pku 1094 Sorting It All Out
本文正體字版由OpenCC轉換
基本方法是拓撲排序，非常容易錯。首先逐條讀入關係，每讀入一個關係，進行一次拓撲排序。拓撲排序可能返回三種結果，有確定唯一的順序，無法確定唯一的順序，有矛盾（存在環）。注意只要一但確定了唯一的順序，立刻判定輸出，即使後面的條件有矛盾也要忽略了。 例如下面數據 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