编程竞赛题目（一）

厚积薄发

5 |3 x3 |. N1 kSorting It All OutDescription
% X7 O  e+ L4 R2 c! o) L
5 v6 X" X' L: ~9 U4 f& fAn 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
+ T' j3 W* v7 ?- F. Y9 Z
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

1 p/ P( z! g( z& u2 xFor each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after ** relations: yyy...y.
9 o6 u1 @2 f: P  T8 j2 I+ _Sorted sequence cannot be determined.
Inconsistency 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.
# {/ g2 s. Z; _! s% G$ K& H
输入样例

. k6 t& z% J2 C* k4 6
A<B
  R# P; k+ F! i7 A% [8 h( IA<C
B<C
C<D
B<D
A<B
3 2
6 u+ |2 W4 c1 _8 QA<B
* {+ z6 Z- Z  a3 n# {- Y% e' rB<A
( X) a  S! s3 R6 z; z26 1
9 T, L6 L" Q' JA<Z
1 O) P& D3 N! o1 C6 h  F- H9 t0 0
: K* }8 M$ c) g$ w  ~2 U- M9 b8 U7 n

输出样例

Sorted sequence determined after 4 relations: ABCD.
7 D" d! G; q) Z, O# W1 g. `Inconsistency found after 2 relations.
6 x* n( m, D% r' j% v# Y: |( b- {Sorted sequence cannot be determined.

3 E: x! A9 a- p; t

Source
+ }/ ^& N/ o. R1 u& |2 w( z
East Central North America 2001

& E$ f+ X% B7 B

程序解题1：

- Q5 }( X4 b( s//By Jackie Cheung
#include <iostream>
. x% m- ]+ T; E2 r* L#include <string>
#include <cassert>
typedef  struct tagNODE
4 K# C+ }5 |# C# V4 l{
6 \9 g2 X0 I6 _$ T- T    char val;
    struct tagNODE* link;
}NODE;
using namespace std;
6 |% u* a  g1 @5 ~3 dvoid Marshall(bool** arrary,int n)
{
8 S$ U0 t7 ?$ n$ E$ @- ]    for(int i=0;i<n;i++)
    {
5 j- B( {4 D4 X        for (int j=0;j<n;j++)
$ }, q7 t9 P7 g; |9 H- y- X6 w. A        {
            if(true==arrary[j])
9 z, k* P1 W; y* V2 C: V' H                for (int k=0;k<n;k++)
5 r# }  L1 ?0 C3 f8 `' d5 I                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
. P; ^" l  h: S) P! a                }
5 y6 D2 i; z$ R+ ]3 B        }
" O- S! V' t# N$ k. d7 ?; j7 c9 j& X  h    }
};
0 ]6 O0 J4 D4 \6 g- p' c" cbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
7 H( G3 L+ }$ u3 ], s' V$ Y    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
3 [( T1 W- d; b5 @+ n1 J7 ~    bool bFlag=false;
    if(1==nLeft)
    {
        Seq[n]='\0';
        return true;
, ^: D( [0 Y: \" H( c    }
' M" f" {+ ?* Q: L. G    for (int i=0;i<n;i++)
; ?( X7 u/ o& U4 ^) P' k# K    {
& \1 c, l% Y( o, |        if(true==array[nIndex])
8 P. ?! t# _0 V8 W7 G        {
            
4 F0 C/ Q+ O. b& t2 [8 A5 q$ ?            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
, y* H& d" {- m( }+ e/ F        }
        if(true==bFlag)
9 J. i$ \% |( K+ U2 ]5 W2 F& b+ j8 H7 y            return true;
    }
    return false;
$ V- k$ k! z6 w0 G3 x. N+ z};
int main()
/ e! t0 n! N  W- u$ A. Z8 G{
    int nSeqLen;
2 i; Z* o9 W' O7 E. ^- {    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
+ V2 ^7 X- R  m, {8 M) @) D8 O# y9 h    cin>>nSeqLen;
" }, |0 T( n2 n5 `* b; S5 Z    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
8 ^# L2 k. ^, x9 j2 \/ w( k* u    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
3 I1 W' P& k& D# t# {    if(nRelNum<nSeqLen-1)
7 G0 {+ b% R9 T/ j1 B( }    {
% y# S: V6 V' g8 o. u" S& F        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
3 g. @# R' S" T( d    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
# G  a4 S) _+ ]! m3 r# J4 B    {
4 g7 L9 s! w9 z8 a7 @( y6 n        cout<<"Input the "<<i+1<<"th relation:"<<endl;
+ `+ D) M) N! V- o        cin>>strRelations;
    }
   
; L& p! |/ I" {# ~    for (int i=0;i<nSeqLen;i++)
6 E. ?" j! A0 o8 E    {
        array=new bool[nSeqLen];
) E6 D0 D4 A6 \. {% C' Y2 z2 D        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
! F( P4 K. Z1 F    }
& O+ O) Z, ^0 Z9 n! Q# G    //The main loop
    for (int i=0;i<nRelNum;i++)
) R7 E  `8 w& i+ Q  Z) g7 J: C. S    {
3 R: g4 E4 m( q        char a=strRelations[0];
$ q. Q) ^3 l' C1 l! o        char b=strRelations[2];
0 V( f3 Z5 V# s. c8 U        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
7 s( q3 b4 A4 Y7 u, f4 q, ]
2 {$ j. N, R6 x        Marshall(array,nSeqLen);

' @" `0 r( F# j( O: _3 y        //Check for Inconsistency after  every relation
, {  G& Q; e* N, H. a        for (int m=0;m<nSeqLen;m++)
        {
8 `& ^6 D2 \1 q1 W6 z# t, M5 n+ c            if(true==array[m][m])
0 D1 w2 V+ m5 h7 \* @1 {            {
* s) ?) v2 v( C2 T0 C4 T! f, A                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
% T2 t! ^# ^$ y8 D                    for(int k=0;k<nSeqLen;k++)
- y1 A6 W+ D5 v& s! G& X0 V8 p                        delete []array[k];
6 G+ J( c9 ~: k' ~5 ?4 v+ v; G% Z                    delete []array;
                    delete []Seq;
                    return 0;
( s2 \3 Q: ]; m* e& D
1 S9 j% `2 w; ?0 |* e            }
        }
: o/ s. k6 k' q# [$ O0 g
; T  B, m5 z0 j/ |# z' y        //Check for the determined sequence after  every relation   
; U; T3 r) Z2 H7 u& N: [8 K' J        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
# H, Y2 M6 K, `$ Z2 c4 l5 F2 r            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
9 @% s7 T0 f, J" G! r. m* l( r6 s                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
( ^/ F# N1 X, a$ \$ x                delete []Seq;
, R7 N9 C+ X1 s- b. X% [                return 0;
            }
& ?6 |  r9 e4 N4 e        }
0 u- O' b8 {! B# s2 \1 P6 P

    }
' E3 W& q" Z3 r    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
6 @3 Z1 j3 t+ W4 p, `9 b    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
% ]/ L  a4 A" J; W1 r3 C" m& o! ]        delete []array[m];
, }( c- l+ }& C/ B7 N; o2 P    delete []array;
5 A6 b6 w$ m' K( g5 e) n% l2 l. m' c    delete []Seq;
  s% U  h# [, {+ n5 l" y   
    return 0;
9 P; N0 G0 n* O/ g/ Q2 K2 p}
6 R! S& G+ l0 Y. W9 @6 }9 m
0 Z7 \4 ^+ ?8 F6 z0 r" W0 v  r程序解题二：#include"stdio.h"
void main()
{
    int n_m[100][2];
    char re[1000][3],
& U. _% ]  q5 ]; l+ G1 N    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
: a# u9 v% O* o# t: [  x    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
1 P& d! j& V6 ~* R( ^' b+ V    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
/ f2 S* p6 W: C    scanf("%s",&re[j]);
  N; o4 p+ ?* A' m: l    }
/ {/ D( Y1 Z& k3 Y6 n6 k! }( _    i=0;
" @# T/ q. n3 d/ p7 M2 H! ^    j=0;
; D7 l. [! D* T# v- g   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++)
; g7 Q+ `2 g' {" }0 J! C# i+ E         for(b=a+1;b<j+n_m[1];b++)
         {
  l, ]2 n* z3 T( }              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])
# H3 R8 V" n7 U0 L" K' I+ k3 u            {
            l=0;
5 P1 f& \& [, A% I            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
3 H! \; M$ l3 `/ ]5 q         }
1 V( m5 m- ^. m) O" Q! \  i0 {      if(l==0)
% ^$ ~9 ]+ e) N  e2 K          continue;//Inconsistency found after x relations.
& N. U4 B5 G% b# ^2 Y7 d+ E2 ?4 j    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
3 y+ T- Q: d; c1 ~! o7 `. C        }
! T% r2 ?6 ?- g4 w3 S9 @        else
% |: Q7 {4 N( Y5 z+ B. U% H        {
          if(n_m[1]==n_m[0]-1)
2 }! r8 l1 m! K          {   
: `; G; O& V: r3 |/ y' y              int k=0,p=0;
3 |3 l5 H4 b  ?" V              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
" Q4 N  f' d9 N) c$ s' N, S                      if(re[0]==re[0]||re[2]==re[2])
                      {
4 I% L4 M' _0 A                      printf("Sorted sequence cannot be determined.\n");
                      break;
                      l=0;
                      }
          }
& V6 n6 Q  q+ o; n# }+ ~        }
        if(l==0)
) n. V( I: }3 \' H) V$ |; R) |        continue;//Sorted sequence cannot be determined.

        else
         {
           
, A7 r  x) A: p. h4 w1 p            for(int k=0;k<n_m[0];k++)
4 p9 j* U) q9 L# O. @$ O# ?             temp[k]=k+65;
, ]& v- f- N3 W& ^! E            for(k=0;k<n_m[1];k++,j++)
6 P: b: k% |5 B  q            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
2 {5 ^. {  e4 `* y              {
% G: |5 y# u# Y* Y! {! K1 J               if(temp==re[0])
" b( B  t( q  r6 F6 b( c( j                   t1=s;
                      if(temp==re[2])
, J! X8 b& b" d$ t, D# @, R                   t2=s;
" h6 g. R3 `- r6 _5 m              }
              if((t1>t2)&&re[1]=='<')
7 Y! ^, H5 I  T, M* q              {
  {4 W: `8 X+ S6 _% X- m                char t3=temp[t1];
0 r2 c. D2 ?8 G) o# }8 J2 C                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
            }
        int count=0;
/ ]3 b( X0 q, Y7 h3 q        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
1 h& z9 @$ g: ]& W; h            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
2 K- u5 \  E# b# n( X" u9 r                count++;
                break;
1 b! e7 o8 R3 c( g* R; s2 C            }
7 t2 |' m$ u& s% ^/ n            if(count==n_m[0]-1)
            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
* A  _- h, [" @3 f; P                  printf("%c",temp[f]);
                 printf("\n");
" o1 B, B4 w6 E, N6 g1 y3 U            }
            else
               printf("Sorted sequence cannot be determined.\n");
0 m; F3 |) \; y9 X8 H        }
    }
    }
( u8 L. {' n' L}
) s+ i+ [, |/ W1 ^; u, x& o" N& y7 W: l
' L7 [1 [7 F8 V. ?5 i. o





  S) {$ e' i0 L
9 D' j& _2 ?: c  [+ M1 l; K0 Y, L

来源：编程爱好者acm题库