编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription
" w  u4 m! B8 M% _: D
: j7 `( J, P. C7 {/ _8 V+ JAn ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
1 y+ J0 j' _& }$ N# s1 E
& a6 U+ p& D* @" ?& H) }Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
! I2 S, X; E, `% Y( W
' p! b4 D: Z) q; \: w1 YFor each problem instance, output consists of one line. This line should be one of the following three:
( J, [' v: G& b; c( `1 v/ `
, p8 l5 q' Z  O% _2 E, ]9 g. N; MSorted sequence determined after ** relations: yyy...y.
* {% o% F, V3 [Sorted sequence cannot be determined.
( ?9 S/ j5 b- t3 H* Y- l1 ~Inconsistency found after ** relations.
' ?- i' F+ y! W
- d  p$ `7 E' x/ V5 Bwhere ** is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
( ~5 S+ k6 C9 L% L* T. F( s6 V
输入样例

4 6
& @/ a% X: o5 _- c8 a. |A<B
A<C
. t3 m) c7 n. k, GB<C
0 ]- x; d6 W6 D- ?, nC<D
; i$ f9 ?2 H# Z! q) Q7 D4 hB<D
A<B
3 2
A<B
B<A
6 Z" l  u4 B: k' u' O26 1
A<Z
4 Z* t% {- w- \  ]2 a" e0 0
8 l  U" O8 y  ]& Q. Q

' U* p: ^8 T' ]$ _输出样例

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
% Q, P. B' c- iSorted sequence cannot be determined.

Source
6 k* {" U9 W0 M! r
1 J4 x. f& g" BEast Central North America 2001

程序解题1：

//By Jackie Cheung
#include <iostream>
#include <string>
: p- u! j  ]# C% t% l2 U/ O. p: V1 T#include <cassert>
+ o! A5 c" m) h  s+ C2 Dtypedef  struct tagNODE
{
$ f8 p5 c( E6 a0 T9 R    char val;
    struct tagNODE* link;
}NODE;
' C0 B% x0 a, c+ {+ C; jusing namespace std;
void Marshall(bool** arrary,int n)
8 S( \* w  q" v{
8 j3 M& p6 s& ~* t. W% S    for(int i=0;i<n;i++)
    {
1 f  K$ X( Z' Z) L/ \        for (int j=0;j<n;j++)
, E/ S6 D7 Z' T$ E! ?: [$ W( I        {
& B5 l6 [+ l& c0 y            if(true==arrary[j])
9 b% Z: |( z. X8 p- @' \6 @5 w                for (int k=0;k<n;k++)
                {
6 {, K: K  z, w  {: @" ?& F                    arrary[j][k]=arrary[j][k] || arrary[k];
$ s8 X" q  q$ O( h! s9 Y+ w                }
$ W1 @9 p- M( u* `* B0 |4 b        }
: F4 |7 k& L" J  V" n0 p    }
1 C) y2 `' V# r7 f+ J};
8 s6 ~  a. Z! w/ u  qbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
; X7 c1 a0 t: J5 \3 G% H: U! p    bool bFlag=false;
, |7 R9 |: e  _6 @4 H2 Z# t    if(1==nLeft)
    {
$ v8 O8 |! k- e  e8 Z        Seq[n]='\0';
9 R8 Y1 g" i; k" G        return true;
    }
" a' K  [  ?" n# k4 g! O    for (int i=0;i<n;i++)
    {
0 u( z3 D* y0 v        if(true==array[nIndex])
        {
1 w, \0 T  o4 F# b$ R+ k9 j7 _& B            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
- p$ G& L2 D0 A. E8 {: r        }
! l; ?0 s, m: i        if(true==bFlag)
+ |1 i$ D7 B0 F5 P8 S- @& F# G            return true;
# u$ d9 c4 W1 k! b) E    }
    return false;
};
& u# f/ t8 @! N% u- b3 h: Tint main()
/ W5 G6 I  c9 m: ~9 e! y2 b( M7 V0 d. s{
    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
) T# e' Q8 C& r& y8 I6 b    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
# D+ i4 T0 K* g0 A' I: w7 W    cin>>nRelNum;
  K5 m$ Y7 |" N3 X* Y) @# O% m    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
8 ]2 v  p. _" v1 h2 }    if(nRelNum<nSeqLen-1)
    {
0 g5 t% v& ?+ R% Y4 i        cout<<"The relation can not be determined!"<<endl;
5 Y# t( {, v. m, S5 ?; g& K        return 0;
    }
: S+ g; o9 r$ a; K, }9 w    string* strRelations=new string[nRelNum];
3 g9 J! O, n" t0 s7 P    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
* D( i' B' l) B) T# c, g
' }7 V( o# [; t( R7 r' |- Y9 O    for(int i=0;i<nRelNum;i++)
1 r1 |, M# }* k" h% g- ]% z* _    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
. N$ W" g4 ?3 L6 |# M   
    for (int i=0;i<nSeqLen;i++)
- m9 E. A1 X& U& i0 {    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
' l5 S! u: K+ J            array[j]=false;
9 Z7 H/ P; Z; W" X; x    }
    //The main loop
# t- u& s7 S, G8 G0 q- w    for (int i=0;i<nRelNum;i++)
    {
        char a=strRelations[0];
* w. R$ T2 |2 o* }5 J( y" I# V$ W        char b=strRelations[2];
7 A1 A' ]4 P7 Y! l7 M        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
( P5 M; ~3 Z! t$ {: s# ]" h. C( {
        Marshall(array,nSeqLen);
% t$ m* E- ]1 j' t# \6 T% z2 w
        //Check for Inconsistency after  every relation
2 m/ f4 h  g7 g- x) u) |/ u        for (int m=0;m<nSeqLen;m++)
# _( c/ f4 B3 z& H5 Q, O        {
0 Y; f8 K5 R" W; {$ ^            if(true==array[m][m])
8 ^) K# R3 U' f* ]2 [3 U            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
5 l8 m7 w8 ~# Y8 K3 Q" @7 R0 A                    delete []strRelations;
3 y* _7 x& n; T+ J4 S                    for(int k=0;k<nSeqLen;k++)
% D- Z6 Y( S& B$ m( m( V# _$ v                        delete []array[k];
                    delete []array;
                    delete []Seq;
                    return 0;
6 n& g+ w" E) D" ]) t  n
& j7 }1 Q' o1 H* E. x            }
        }

4 h! `7 ?6 C) W6 h* v. x" A8 p  W        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
; `3 D- u. h5 b2 c- h0 u        {
4 e/ s/ Q: E" C% Y( s$ y            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
$ K7 ?5 K' M' _3 [- o# D% c                for(int m=0;m<nSeqLen;m++)
; X: K4 z. A; ~  O$ {, c! O                    delete []array[m];
                delete []array;
                delete []Seq;
( [+ c5 }3 M2 `& f$ H* D4 L                return 0;
( s' u4 f/ U4 X/ P* U            }
6 }7 p+ v" n0 Q0 i9 x+ p        }

0 `' H% T! I8 _6 T: Q8 ]' q
    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
5 Z9 Q) }; g$ e) c8 S    cout<<"The relation can not be determined!"<<endl;
- r$ X( U% a0 {0 x, i2 i    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
9 H! o( f) L! F5 Y. @6 O: f' ?: l        delete []array[m];
    delete []array;
' e, y( b- S; o0 e; b    delete []Seq;
7 C/ V& F0 e+ T3 s   
; X1 o1 d0 c2 V5 N1 C2 m    return 0;
}

5 A. S# x) [1 F9 s程序解题二：#include"stdio.h"
/ d: A/ z( ^6 \' mvoid main()
{
) g/ H: A$ v& ~" ?# {5 r( G    int n_m[100][2];
. n, u; v  S1 |% h' G  q    char re[1000][3],
+ R) X7 U6 x' e+ z& V$ O    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
' P! k$ ^( m$ s. s. y    while(n_m[0]!=0&&n_m[1]!=0)
4 Z4 O; j; G; S+ _8 w2 S    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
! F( S$ ?" N0 s- w# ]* a8 G( N    i=0;
  p# \2 p0 ?2 {# f    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
# N" c( D# v# E# i2 F; ?% G4 G       int a=0,b=0,l=1;
) U& z- w: {* W6 C# C       for(a=j;a<j+n_m[1]-1;a++)
( e; i* ?- f# d0 ]2 ?         for(b=a+1;b<j+n_m[1];b++)
  [' I. i( c  S         {
7 n5 m  ]5 Z, z9 Q8 G5 V  L9 Z5 [$ T. r              if(re[a][0]==re[0]&&re[a][2]==re[2]&&re[a][1]!=re[1]||re[a][0]==re[2]&&re[a][2]==re[0]&&re[a][1]==re[1])
            {
            l=0;
/ Z8 j0 M. O8 F' v' }: Y$ [, @            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
' O4 z1 G3 O- Y9 j" d/ Q- f/ ^( F         }
      if(l==0)
  [5 m& x# {' z) i$ A" ^0 o          continue;//Inconsistency found after x relations.
9 C1 T( e' b( T* r8 k# S$ V2 u    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
- ~0 W; p6 Z/ k+ a" d: J            l=0;
7 P: i& x" [7 R        }
5 }* @, J# r! V- T$ x" R/ J/ f        else
, u1 H! [5 r" M9 O5 t! a) @+ {        {
          if(n_m[1]==n_m[0]-1)
' ^, \, t! o: @/ ]& \/ S! u          {   
              int k=0,p=0;
  T$ R) `! Z8 k8 X. J              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
: u" \  m. X" k& \. U, x8 z8 P                      break;
" p/ @+ F- n$ E' u9 Z: c                      l=0;
                      }
          }
        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.

% r3 t# f+ ~* `& d7 ^" q        else
: b! R9 T" u7 @         {
0 D3 D, z2 n% }; V# e+ |           
+ A4 R, \! h! Q* F& @            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
4 @! i& L1 P$ l6 X/ |9 q, t1 C3 p' j            for(k=0;k<n_m[1];k++,j++)
: H2 I- H* q1 a& H2 B+ W. N            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
5 Z* C+ u- J! A, |1 z2 \) t              {
! ]1 T) y1 h% X* I               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
" @8 B; t" @$ p6 N3 m1 @5 c1 l6 Q: j                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
% X; H" E9 c" E( e$ B              {
# e5 w6 c5 v7 e# q1 O; Q3 U5 U6 y% c2 _                char t3=temp[t1];
' g; h# y3 k4 Q& V& L+ m                temp[t1]=temp[t2];
0 A( T, _3 ]1 t9 W4 l* i6 i, K* }                temp[t2]=t3;
              }
+ Q% r$ M; @8 V. \5 @            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
4 F; J! o' `2 S3 t        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
" ?: U. e5 d, T  a            {
6 m6 N! G# q4 `, N                count++;
                break;
0 I( F* L, R# R2 |, e# Q! a            }
            if(count==n_m[0]-1)
9 \+ E0 [$ ]6 u            {
$ n; B* A2 T+ [7 `; y* K* F, m0 g                printf("Sorted sequence determined after %d relations:",n_m[1]);
* O8 P( F; ^! u                for(int f=0;f<n_m[0];f++)
( o. W4 g. J8 _  E2 Y8 p                  printf("%c",temp[f]);
  {" n0 _' _7 j3 `+ e4 g* w! ^$ w                 printf("\n");
6 R: w# n9 J, S- Z4 s6 s  x            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
    }
7 [  A4 F/ t# @) d% e$ H4 S    }
  Q& \0 G  ]% S; F; K/ c7 z}
$ A4 ]! U, w8 U

+ M9 c& Z9 q& `

9 X7 x1 v2 z( V0 N  w+ T

6 K4 ^/ w, \* _. U% m6 B* a
: Q/ K; r* x4 j8 m6 _
. h0 b1 X2 b: |

来源：编程爱好者acm题库