编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription
7 P. Y( Z/ Z: O) N: g
An 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.
8 R- i, U  D; wInput

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

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after ** relations: yyy...y.
2 `/ L1 h" i6 o+ v) qSorted sequence cannot be determined.
4 V8 c* C2 A  D: v* F' PInconsistency found after ** relations.

where ** 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.

" I; y: _# c8 e5 d1 ]输入样例

4 6
9 s4 D5 k0 U6 f1 a0 fA<B
A<C
B<C
+ b" _) D  l7 Y0 a  q! BC<D
B<D
A<B
3 2
$ U0 y# B; `4 _  j3 eA<B
6 [! B$ V5 q8 o1 C5 Y. RB<A
3 ?3 b; L# l! M7 P, c1 I5 o( R7 ^26 1
% B: |6 H. u9 s; @! w/ O4 m  yA<Z
0 0

! I  o: q1 l0 P/ B7 S输出样例

1 c0 H2 }) w, t- WSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

8 ~" [+ g4 V' K) L( R8 U! X5 a

Source
+ I) r4 U6 }; M
  G; T) t/ G/ O) qEast Central North America 2001

程序解题1：

- {1 f; U- J( k# l+ i1 p//By Jackie Cheung
#include <iostream>
3 p$ H# D, M3 E#include <string>
#include <cassert>
' Q; [' O4 d& ~7 f: w; `2 Itypedef  struct tagNODE
{
    char val;
    struct tagNODE* link;
3 V3 ]- J! M9 `8 ], S  O}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
6 Z2 ]4 p- x4 c- [) ~{
2 E% k4 ]; ?6 m" O    for(int i=0;i<n;i++)
* B, s7 ^/ L( J- A5 S' u    {
        for (int j=0;j<n;j++)
' \" }, m- X+ t! ^3 o' i3 l        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
  ~. \& h6 a, s* O% H( E# y                }
        }
/ `/ I9 @! n: e1 d* Q    }
};
8 ?" p3 v. l, }/ M6 Q  Hbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
7 p4 R6 c% ?9 A# L% b/ T* @{
8 Y" h+ x! X% d1 s; @# [    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
+ j$ G+ A" d! g        Seq[n]='\0';
        return true;
; W9 a9 W5 _: n& l  d    }
5 I5 A3 B* b* M  m( |0 a    for (int i=0;i<n;i++)
) u& E1 U! Z. ~    {
- `9 q* L  _( I; \0 Y        if(true==array[nIndex])
        {
            
1 S. ]( v7 ]7 X( T4 s$ k            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
    }
    return false;
3 d( y3 d+ r, a- j" ?% Y};
int main()
& ~; R3 `/ C/ Q{
! \# E4 S/ `/ P' i6 q    int nSeqLen;
8 E6 p; _! G0 n! Y- r% x0 W" y    int nRelNum;
0 p3 p* {' V5 o$ i    cout<<"Input the length of the sequence:"<<endl;
4 Q# Z2 w3 r; }$ M    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
. e5 _1 I0 H8 y, c  \0 A4 R* D    cin>>nRelNum;
4 x. v; H& Q% i6 h    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
- q- P2 }2 N( ~3 g    if(nRelNum<nSeqLen-1)
    {
        cout<<"The relation can not be determined!"<<endl;
1 J6 }, ?8 s. W$ x( K! p        return 0;
    }
6 y& J; G; H0 k. n+ r: @    string* strRelations=new string[nRelNum];
. V2 J) Z3 A( v+ r. J& t4 v* @# }    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

1 d- e3 ]$ p7 R3 }1 }5 u: x    for(int i=0;i<nRelNum;i++)
    {
. y+ f0 }; x' o        cout<<"Input the "<<i+1<<"th relation:"<<endl;
! }6 h# C! j5 a        cin>>strRelations;
    }
   
    for (int i=0;i<nSeqLen;i++)
    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
    }
    //The main loop
; P# M+ q' x6 c1 f2 t* v8 {    for (int i=0;i<nRelNum;i++)
! v) B8 |) V+ P; t9 l" ^; }; d" D    {
        char a=strRelations[0];
        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
+ s- U9 K2 A9 z/ w! K( P) z        array[a-'a'][b-'a']=true;

' k9 [  l; q9 c8 ]        Marshall(array,nSeqLen);

  c# K6 G  w1 U        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
! ~0 t! _+ s+ E6 f            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
, Y% b$ K3 c8 v0 @9 A* L* e1 }! d                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
2 }, b3 t: n, Q: E) v$ f                    delete []Seq;
3 N  v  z# f" M                    return 0;
  j8 V+ v  ^4 j: h; s
" t3 n; {( F( V! J2 f0 t            }
/ c4 I  u* b3 {! J9 P; |+ m        }
! \% c8 v7 J) [+ Z5 F
1 S$ e5 r' K/ ]6 u0 c7 e- U        //Check for the determined sequence after  every relation   
6 x% g) ]) k7 U9 g0 n+ G8 T, `        for (int j=0;j<nSeqLen;j++)
        {
  N! W3 J% @9 \7 P            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
! e. \) ~" M4 _( R& M: s$ D            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
/ p4 t, Y9 f. k2 g- Z                delete []strRelations;
8 {. L. u+ s8 C9 z& o                for(int m=0;m<nSeqLen;m++)
5 B8 H6 d% x) C# s3 S5 V; i                    delete []array[m];
                delete []array;
6 n! y+ B' d9 s9 E8 P                delete []Seq;
9 k( F$ N" H% d/ N                return 0;
5 [' y5 [( B' w- |) t+ M            }
        }


    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
. A7 {* T1 `' H; ?. m0 j6 L8 ^        delete []array[m];
    delete []array;
8 T4 Z8 w# P, Y7 p+ o: `    delete []Seq;
- c3 z2 z& n" L8 t4 z  R   
    return 0;
0 O. V; K* U9 f& p$ s0 \7 r3 C}
7 n5 B, }+ b, w; \
程序解题二：#include"stdio.h"
void main()
& I/ y( m4 p/ ?7 ^2 m1 C% D' |{
/ S9 ]. R, _5 u! h+ P    int n_m[100][2];
5 ~* @( f' H1 s1 k# c- p; ?. E    char re[1000][3],
    temp[26];
    int i=0,j=0;
: v. S/ R; j) N    scanf("%d%d",&n_m[0],&n_m[1]);
1 }7 a- a* U' m! [/ }: l    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
* S3 Y# ~2 ]$ E6 p, O' y    while(n_m[0]!=0&&n_m[1]!=0)
+ B4 g: W* {/ P3 h0 J    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
" ^8 \# w2 m* x) z    for( int f=0;f<n_m[1];f++,j++)
8 n" {! r# [  z6 d+ x* c: z    scanf("%s",&re[j]);
1 L5 A/ Y  N5 d    }
    i=0;
    j=0;
. ^2 _5 ?: J* j) B   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
       int a=0,b=0,l=1;
       for(a=j;a<j+n_m[1]-1;a++)
& L0 G2 N  m$ n" i& ?         for(b=a+1;b<j+n_m[1];b++)
         {
              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])
( J; p2 E; F& y+ r            {
            l=0;
& F. V  x! r, [% h$ c1 g# g            printf("Inconsistency found after %d relations.\n",n_m[1]);
  Y/ Q  s+ |7 l9 k) V: H' Q            break;
+ Z) H) [! f/ b6 k8 u) m            }
         }
2 T- K) K! F/ S7 Q      if(l==0)
/ d7 C: T0 R; ], `          continue;//Inconsistency found after x relations.
% ?" z9 ?7 K3 D0 _2 k, R+ L) k2 |: n" A    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
  ]) ^9 t, B! b! `            l=0;
$ S/ `* Q+ h+ t- M        }
        else
- P  }+ B/ S& B* k/ ]0 R        {
4 I& u* c  ^% I8 o0 ]/ {          if(n_m[1]==n_m[0]-1)
          {   
) V$ e9 }( P+ y9 D- Y              int k=0,p=0;
( i9 t1 f/ j9 s- Y              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
9 G: U% o1 b. D+ a% \' w; \                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
                      break;
4 D4 d: \# U& d9 B6 A                      l=0;
, ]$ G/ J* [- J8 \9 E. R                      }
3 N: k* q1 G. n8 m6 g$ o  o# Z- C          }
        }
' c8 w, B0 W4 G/ g8 O        if(l==0)
        continue;//Sorted sequence cannot be determined.
2 |9 h8 \8 l6 D' h0 H2 p# V
6 P- E8 U: l0 z6 d! ^4 m% r) ^! ?        else
         {
           
: I: P/ z3 n0 C* x* c( I6 m            for(int k=0;k<n_m[0];k++)
+ y3 G" A' x, P, n             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
1 I% W5 m2 Q' a! z            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
6 ?% }3 u7 G$ @+ G  x; z1 o               if(temp==re[0])
                   t1=s;
2 W. w0 Q* l+ _& ]# m3 E                      if(temp==re[2])
                   t2=s;
              }
3 A5 _( _- L0 @              if((t1>t2)&&re[1]=='<')
: }7 Z6 ?1 ^8 \7 i              {
; ?- s  z* C! P* `  W5 x                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
7 U2 k* i( F; i) O                count++;
                break;
2 H# x! o1 r3 ?7 `' y; W# \            }
            if(count==n_m[0]-1)
5 l- m, S( `& ]- ]. l            {
3 [# m( ^8 P* n) c" x                printf("Sorted sequence determined after %d relations:",n_m[1]);
3 R* Q3 I. f' S% F# J                for(int f=0;f<n_m[0];f++)
: r5 v6 j6 m  s# o4 j8 f                  printf("%c",temp[f]);
                 printf("\n");
            }
+ W# u' b! I2 }" ?( R3 W: s            else
0 L; P8 B' D3 [. N9 j- {1 u               printf("Sorted sequence cannot be determined.\n");
        }
. c" |  o3 O- Q5 Q/ T4 O    }
$ ]$ K6 n  Y: |/ Y5 F5 s6 u8 _$ c    }
" r; R9 |, z6 U, P4 x+ L) z* ^}
& N! W; ?9 @! u% A" d
6 h6 |9 g' `( V$ E: F
, y7 ^& E& Z; e! ^9 [; m


0 i. I6 c  a! m
% w, _1 A! X" n7 j1 V' j

! H3 |$ E/ t8 Z% R! x

来源：编程爱好者acm题库