编程竞赛题目（一）

厚积薄发

2 ^( G% S8 F+ ?1 @* P8 y0 d
Sorting It All OutDescription

: T, c0 t2 ^. |* F8 U! @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.
Input

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.
. z3 ?4 a4 Z) N  P7 z" q$ @" |Output

) ?1 d/ I8 X/ bFor each problem instance, output consists of one line. This line should be one of the following three:
* Z. S2 o) i' e6 j8 Q4 A! i
! V" B5 x% \) R9 v0 |Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.

6 g. l; _1 e  R& U; Hwhere ** 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.

! C% p& n1 ~+ p  K# r0 }2 e& ~4 Z输入样例

) Q% Q) ^6 c5 N2 \: Z4 6
A<B
1 I( ]9 d& J+ e$ c$ f6 N+ k" uA<C
B<C
2 e% E! A1 U8 V) l6 M# AC<D
B<D
A<B
3 2
6 s: @4 U; ]( n( o2 P& VA<B
B<A
  T& f; x3 w+ k6 S0 R26 1
A<Z
: |: e8 m) o4 R. d0 0

输出样例

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
7 G) F+ X4 d$ d. F" [5 m8 SSorted sequence cannot be determined.

& t6 }, z$ Q' o$ x' u

Source
$ r8 c( p" p; [& u( M) B
East Central North America 2001

0 M- B" J& t8 o: E5 [3 Q% A8 R

程序解题1：

( l! h8 A1 s/ B# j. l- v& t' Z9 n" m//By Jackie Cheung
6 T8 {: s. E5 D) _#include <iostream>
#include <string>
#include <cassert>
typedef  struct tagNODE
{
    char val;
0 N6 j6 f  o4 N& p9 L3 g2 ~    struct tagNODE* link;
! B+ w' F5 g" W8 d}NODE;
6 {/ U6 @% O$ ~4 r7 u  Pusing namespace std;
void Marshall(bool** arrary,int n)
9 ^3 R# u6 w1 S+ x. F8 i{
8 J: y6 a  j+ @/ T    for(int i=0;i<n;i++)
    {
$ W3 ^2 N, ^" B        for (int j=0;j<n;j++)
        {
) I; R3 M* r* }. u1 W, W1 u            if(true==arrary[j])
                for (int k=0;k<n;k++)
1 B; V8 u) \% z1 m/ R" `                {
9 W1 j: b2 G+ F" y1 Z4 o) v% e- k# y4 Y& V                    arrary[j][k]=arrary[j][k] || arrary[k];
% h8 R7 b/ e% P3 H: I                }
$ D2 q; }* E& p# ~5 H# k& o        }
8 _: l5 _7 r# ?5 S5 t  B    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
* W: Q# ]) y5 u1 w2 {/ M1 u{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
; u0 e# z4 n' Z! N0 c8 B    {
. X. |- s$ u/ m        Seq[n]='\0';
& j7 K% g" w7 I& J! ]! \- K        return true;
4 B, [3 B7 `: H4 a# W+ M    }
# i7 Q+ Q0 b  x, T* ?4 [. D    for (int i=0;i<n;i++)
    {
  B; u2 B6 ~7 V; b, n        if(true==array[nIndex])
1 D2 B; j  r- v: T: J        {
            
2 z  e6 e/ I3 z0 K; a; n% S  o            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
1 A! L- J4 z% p7 Q        }
  y; j  L! a; ~# o5 ^& K        if(true==bFlag)
4 I7 h7 Y+ r7 n4 _            return true;
    }
    return false;
! I0 p. T* ^- f  o0 a( V: h};
int main()
{
    int nSeqLen;
    int nRelNum;
2 {" g9 `& n1 h  q8 M: ?  L2 E    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
$ s* T- }/ a7 ?% \4 @0 v    cout<<"Input the number of relations between the elements:"<<endl;
) `7 c. S. E3 B! I- v. q    cin>>nRelNum;
1 P* m% c- r9 ^: b    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
3 I3 M" A( L1 o) m2 |0 u    if(nRelNum<nSeqLen-1)
    {
" b- G8 @& d& x' ^# n! G6 t0 e3 I        cout<<"The relation can not be determined!"<<endl;
# h, ~9 y: ~6 }5 `( ~        return 0;
    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
: b2 \) z, k) I+ w6 Y; B/ N
    for(int i=0;i<nRelNum;i++)
    {
1 K  l, ]5 L/ ~. E9 u7 Y        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
   
1 O# T) R) x# H! {  H2 S    for (int i=0;i<nSeqLen;i++)
5 }* M: \" n8 X. ]    {
0 Q# S) E6 f0 q' A1 Q' O        array=new bool[nSeqLen];
) L7 {" u$ H) J$ V5 n7 M; u$ ^        for (int j=0;j<nSeqLen;j++)
/ ?$ o2 l. o; j7 }% K5 Y% u            array[j]=false;
, |- l. @1 m" H; R    }
; T) X9 b% \8 s% r4 e' R    //The main loop
8 R+ ^+ b% C! E0 W% T    for (int i=0;i<nRelNum;i++)
. d" N9 h5 e0 T2 C    {
        char a=strRelations[0];
+ H! J+ y/ b" b        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);

        //Check for Inconsistency after  every relation
* z8 W) \$ \7 S. z3 ]8 h1 v3 b' G        for (int m=0;m<nSeqLen;m++)
  X. ?, j5 w" z8 ^0 x8 t        {
            if(true==array[m][m])
            {
2 `1 g$ s, r. }3 s2 Y' w3 @" Z6 W5 X                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
+ h2 ~+ c2 |$ Z$ h+ U6 C                    delete []strRelations;
( H' f9 V6 ~/ ?; |# e' g                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
! k- [+ v9 N: e5 r# G, {4 P                    delete []Seq;
' S& N/ w2 w1 Q; p                    return 0;

            }
( O" d! i! s4 x. k2 n        }

6 K, F( u( {& Q5 g        //Check for the determined sequence after  every relation   
  B0 n, A4 A3 ~0 g, [+ r        for (int j=0;j<nSeqLen;j++)
        {
1 ~  C# d% j$ W$ {+ ?8 V" C) v            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
( `5 R0 K4 w2 N! {$ u            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
5 i/ Z0 u- ~, B* b9 }: k) y                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
  j, X" P. N  n9 |+ _                    delete []array[m];
) K& k* I  R2 ~5 A. u9 t                delete []array;
, Y, {" g6 j7 U, T  A9 e# N                delete []Seq;
7 p5 u- E$ i5 `0 r* q2 Z$ g/ \                return 0;
: T( u4 y7 N; y, h! M            }
1 _% L0 o: t+ c/ f+ M# A$ ?' _        }
0 v. x% ]  N: v
, M$ g: u/ n. C% I$ m
9 h' z+ \6 r1 |7 W" S, Z    }
, p9 J  K) z7 {2 V- X7 X    //If the program has come to here ,then the relationship hasn't been determined!!!
) S+ D& S) h7 W, d    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
8 t8 ^2 }1 G3 J; m" n( _    for(int m=0;m<nSeqLen;m++)
6 s" g7 \% H. }0 Z& F        delete []array[m];
    delete []array;
    delete []Seq;
. z$ I* A2 W! w" ?+ }   
7 P; p% `9 T: k    return 0;
" g$ g) F% o1 s9 a4 o. w}

7 {+ E; Y. y0 N/ Z6 X/ t程序解题二：#include"stdio.h"
void main()
) t0 @8 w3 G1 F' E# Z- K4 W: }{
+ R+ ?1 H( G( W    int n_m[100][2];
    char re[1000][3],
+ _# ]' L0 O& f( {. L1 P( q, R, S    temp[26];
9 `) x! B; u. k" \5 b5 D0 H    int i=0,j=0;
! a9 Q/ h$ w) ?- s" e    scanf("%d%d",&n_m[0],&n_m[1]);
. H+ w: e* T- p1 M+ Z) q    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
% ]- D( G' W4 v: z    for( int f=0;f<n_m[1];f++,j++)
7 d! r4 l; ]2 h    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
- \7 y$ n" T/ l7 d7 }   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
% q# f: a) N  y9 B' n* [2 U% T/ F# Y, l       int a=0,b=0,l=1;
1 a0 S; r( t, g       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
         {
0 i/ T! h/ y) ~# r6 g0 c              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])
            {
" i1 v6 J% R7 {5 N4 _: J            l=0;
- T: w+ X& O4 @! R2 o+ [2 R            printf("Inconsistency found after %d relations.\n",n_m[1]);
; M  t% e( q, f1 h0 r( r. P            break;
0 ?+ ^: C3 w  J# N. S/ a            }
% r1 g/ _( u$ A2 |" |, r$ Q8 ]         }
: t3 l4 r4 _/ f& C: ?+ G: ?      if(l==0)
5 t! ~/ b# u! X* }* J0 Y          continue;//Inconsistency found after x relations.
% S" l: v: k; n4 p( e, r4 p6 B& k    else{
           if(n_m[1]<n_m[0]-1)
% s* p' S% B/ {- j5 z        {
            printf("Sorted sequence cannot be determined.\n");
2 r9 {4 B, |2 \* l2 V2 i            l=0;
        }
        else
- P8 e+ H9 X4 x        {
          if(n_m[1]==n_m[0]-1)
' [) m$ K9 B% e, E' G: \          {   
              int k=0,p=0;
3 T, X; y2 o7 `, n( C              for( ;k<n_m[1]-1;k++)
) U! }6 {9 S# X7 i; p                  for(p=k+1;p<n_m[1];p++)
0 c9 B' R2 C3 c  T: V9 s* M                      if(re[0]==re[0]||re[2]==re[2])
' P; M( i8 f( l  Q                      {
                      printf("Sorted sequence cannot be determined.\n");
+ c2 ^5 K; f0 P& @' U                      break;
                      l=0;
                      }
          }
4 ?# _8 \+ ~0 w; ]7 Y8 t9 X. D, U( i        }
        if(l==0)
1 I0 D) s% O$ }( V$ X+ X        continue;//Sorted sequence cannot be determined.
* Q) I* G( h. l( d# `* z. j7 N
- `7 _" E) A3 x# B. [! I        else
. `- w$ m* S! @( v' d         {
           
            for(int k=0;k<n_m[0];k++)
* \: c- C5 |7 _5 y8 y4 G. P& ]             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
& e  l- B6 f7 e1 r; d            {
1 l5 Q! J  C( @  b1 p4 R/ b+ w                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
$ N( G0 N% R' p* o3 Y5 m               if(temp==re[0])
                   t1=s;
3 t& \  `) j0 h6 r; G  H+ b                      if(temp==re[2])
. D5 ?8 f- n% L1 u. x                   t2=s;
$ U7 u4 A% _0 c! B" y9 t              }
              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
                temp[t1]=temp[t2];
9 m8 |! G% ^, S  V, I0 Z                temp[t2]=t3;
              }
8 z/ _1 ^: Z) E; a! N            }
        int count=0;
1 |( W9 `* V) x6 w( B        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])
* W( A! P( f$ w3 H            {
                count++;
                break;
            }
" b2 ?3 v+ U. d            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++)
! d' ~! s/ M$ d0 n                  printf("%c",temp[f]);
                 printf("\n");
            }
3 b  P( A/ G: z9 M5 R7 x% P1 U            else
               printf("Sorted sequence cannot be determined.\n");
        }
% _% X. S. Y* w5 _! N8 [    }
7 j6 d- [: F8 R! _    }
}
- f# ~; e* Y4 d; u* u
' j3 N; P0 ~8 E7 t; n, w

5 r8 V7 T7 @: c
% n3 p# E  b5 u5 C( ]



9 V( m9 ]; @# ]$ e

来源：编程爱好者acm题库