编程竞赛题目（一）

厚积薄发

4 x$ l! J9 k$ N$ h/ Q! t, @: ^; d) n
6 @: `' \! i0 USorting It All OutDescription
: N9 [" }) ]! Q  ^& [4 V( X
3 b- @3 c# b; G6 Q. CAn 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

) w: U5 J; B8 E7 X  B5 B0 CInput 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.
& `7 p- M4 `; f  cOutput

For each problem instance, output consists of one line. This line should be one of the following three:
3 f8 @* V, p" O: \
8 S; C, \& }0 p3 n, w7 Z5 c# sSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.

* e# L$ p+ H* D. w+ U* Kwhere ** 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.
6 b: r8 a" s, ^3 A# N( e2 G+ p
, ~. S) T2 S5 Y  g6 e输入样例

. r1 J% l/ ^% m4 y. q  T- g1 A4 U' `- D; r4 6
% i. E1 I: ]# m$ b1 `A<B
A<C
9 h. v$ C. o' ]. r9 j& b1 b1 l* CB<C
" n: ^- g' y2 y( G1 B5 \, MC<D
& ]& e# B# L# cB<D
3 g& P( ~% \& i- @3 ?% H  v1 wA<B
3 2
A<B
$ ?) L5 z! V8 c0 WB<A
26 1
A<Z
0 0
6 ?$ t( y! u, j6 y7 {& v1 X  _

输出样例

- L/ V' B; k" ]& @! [; K8 lSorted sequence determined after 4 relations: ABCD.
7 t6 J1 }, \. aInconsistency found after 2 relations.
$ c7 k: ]8 X! b2 o; {1 PSorted sequence cannot be determined.

4 E' n: l& Z  d$ S# P

Source
+ Y: l7 U8 U( e* o
East Central North America 2001

3 K0 }8 o2 w6 V; o5 ^1 j

程序解题1：

//By Jackie Cheung
#include <iostream>
#include <string>
% I- Z: j3 m2 n+ N#include <cassert>
, [1 ]: G* L0 T2 N( x0 }typedef  struct tagNODE
+ g( [6 o1 A5 y/ T$ ^' r' ?+ j{
1 l) T+ Z' d! Q; s0 r* H( q$ A    char val;
2 q. i$ }& _6 \1 N+ F    struct tagNODE* link;
+ [- O  u& H7 C% _) g* ^}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
{
7 `2 r, q/ x; K! F, v6 o    for(int i=0;i<n;i++)
4 W' n/ A+ X# e    {
# W9 x+ |- s, P& p2 r7 A        for (int j=0;j<n;j++)
- o' ]$ o: H  l  i        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
% d3 K: c: e* H6 c' T                }
' t$ d8 j# ~/ Z  q% l8 B4 F: I        }
    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
! ~6 _9 h- O6 V# s/ Y1 w. ]4 y, ?{
/ d) v9 |+ e1 L2 S    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
& o2 V5 s% V! H. d/ }    bool bFlag=false;
    if(1==nLeft)
    {
6 R- r+ l. f8 z# Y/ r; Y2 m        Seq[n]='\0';
        return true;
. H6 ?9 U1 [5 y: ~1 H& [9 M    }
    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
        {
" B+ l8 E/ j- m: e# g            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
; w5 x8 ?- {5 N* X        if(true==bFlag)
            return true;
    }
' X7 `$ N  b0 t0 f. m# L$ b6 r    return false;
};
) W! l5 [9 o' f+ w7 Mint main()
{
    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
, B* ~+ \5 v0 U: n- t1 d    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
; l. ?" t  a5 U7 L: G    {
        cout<<"The relation can not be determined!"<<endl;
: j# T# l  M  z) j6 B5 F+ Q2 A        return 0;
& q$ t$ C0 d" F3 i# K4 J: H+ j    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
- B$ u( c, {; l    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
4 [. z8 ~) d7 t% g' h    }
   
6 ]4 F& l8 o: D( F* x  i# X    for (int i=0;i<nSeqLen;i++)
    {
9 o+ i4 N  m# A        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
1 h# g) J2 ?1 P            array[j]=false;
% W2 Y  t/ H$ L# \4 {' W0 ]    }
    //The main loop
, |, Z3 g+ }8 n  U" J    for (int i=0;i<nRelNum;i++)
# N8 k9 y/ f2 A& w    {
        char a=strRelations[0];
        char b=strRelations[2];
- K5 N6 @8 _5 B/ X6 {+ A$ ?) ]        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
- ]3 _: O0 i  Y1 _2 W        array[a-'a'][b-'a']=true;

8 k# n: J( N8 _' }4 F& Z" a        Marshall(array,nSeqLen);

        //Check for Inconsistency after  every relation
$ ?( s% ]( ^: p$ N, H5 i        for (int m=0;m<nSeqLen;m++)
        {
2 t% I0 o" R1 p7 e6 z            if(true==array[m][m])
/ B: {  j3 Z4 L$ @+ g6 D. s            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
7 q% g- l  c" h6 `, l1 n$ U                        delete []array[k];
                    delete []array;
$ C1 R- N) x1 v0 x" ?1 [, ]                    delete []Seq;
                    return 0;
4 f. o, G8 N' ~( U  M
            }
        }

        //Check for the determined sequence after  every relation   
) |! Y! L9 P+ u3 x: C6 L        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
5 v1 K7 g& b8 s* U+ i1 A6 q            {
( |% ]8 Z) O& X  x                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
2 x( |# Z7 y; l0 }                for(int m=0;m<nSeqLen;m++)
) d7 E# p! {: s9 |                    delete []array[m];
5 O2 @( x0 I7 u                delete []array;
                delete []Seq;
                return 0;
            }
        }
2 O) g! ~  V, {, ?) I# i2 b+ `

    }
3 N0 k. ~/ |9 L9 f    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
( G6 M$ C9 f7 I- Z& H8 j3 [    delete []strRelations;
- K8 D* M- A9 N4 E# B  t( a    for(int m=0;m<nSeqLen;m++)
" Y) I. X, c2 U: {" Y7 H        delete []array[m];
7 F: K$ d) u& r( _! w    delete []array;
    delete []Seq;
   
    return 0;
" F! H) {; j9 `1 ^, G3 H5 u}

* o+ G2 g4 U" k; x3 A! L% y程序解题二：#include"stdio.h"
8 A& v+ c2 v1 f' c/ uvoid main()
{
# _, `( ^* S- b  N4 W" W    int n_m[100][2];
    char re[1000][3],
# o  [- P* j; u    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
" a# t3 g5 H2 g' j    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
, l6 C' u! Q  ^! T* p/ d7 Q, J    i++;
4 s3 R) \6 @" L3 k    scanf("%d%d",&n_m[0],&n_m[1]);
3 B5 E7 j- M0 H    for( int f=0;f<n_m[1];f++,j++)
! z) u  C" |" T5 {5 M  ?) T2 }    scanf("%s",&re[j]);
    }
9 w% P" \, a. b( {. Y1 v    i=0;
    j=0;
9 S+ }( Q& Q! \0 Z) A' w3 V2 G   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
. O" X; h) I. p& z( Z    {
) b6 E4 n/ J! l& v       int a=0,b=0,l=1;
5 {: j; j: L6 Y9 c) P) P3 I: `; Z       for(a=j;a<j+n_m[1]-1;a++)
# R, f1 \5 t, i( {% y1 u7 W         for(b=a+1;b<j+n_m[1];b++)
/ }7 g. d1 ]2 J  ~' 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])
            {
' [, {7 y* r, P* G            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
1 O* t" C% p( L! t            break;
            }
  ]% u# C5 k) n3 S         }
      if(l==0)
, Y1 }/ I& W# a5 m9 i          continue;//Inconsistency found after x relations.
0 L8 t, @, K9 E. T) S    else{
           if(n_m[1]<n_m[0]-1)
/ L  \( |) Z0 K0 f; o& A        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
) Q4 M3 w0 @- s4 m: ~5 l  p! P4 i        else
        {
$ U3 T! ^  `" L7 s- m% l& F6 Q' w          if(n_m[1]==n_m[0]-1)
  I: i( s) O+ N& r          {   
              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
5 }1 {1 L7 ~& ]) U                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
; v' ^. I$ w, a  g% I& a                      break;
                      l=0;
                      }
  Q+ |- s4 p; {( |          }
        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.

% ?& y$ d8 h8 A        else
$ x( `" ?1 Z' X8 G4 `         {
1 D' ]0 q/ E( h) ^& c           
2 Q  s( V: O' M5 |  B            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
" j$ F% f6 {% T0 _4 h  d2 j8 Q            for(k=0;k<n_m[1];k++,j++)
# x( i8 B( ~/ _' M/ s  n- r: {; p            {
                int t1=0,t2=0;
4 E7 a: I: H$ @" A% y& v6 f              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
9 N- |' w$ L$ [. |( f& L                   t2=s;
              }
+ T8 E% m4 V: l2 q# ~8 h              if((t1>t2)&&re[1]=='<')
! O5 V! k2 x1 @3 [5 ~              {
. C$ h. L) |0 x( S- m% z) G$ W. f  R7 \                char t3=temp[t1];
                temp[t1]=temp[t2];
9 s3 m0 H. r1 C, b, ~1 q                temp[t2]=t3;
1 r" \2 n. A3 [              }
            }
        int count=0;
! a  i: R5 T# f1 _( e        for(int s=0;s<n_m[0]-1;s++)
9 }0 C2 [6 t$ z9 v/ F3 D        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
  u8 a, ~5 w; ^5 n9 f0 d( p* P            {
' g4 u" E, O3 n: A, N                count++;
                break;
3 J* Y& Q. n6 P3 p7 N            }
& S! q; f7 c  T3 d) p, O9 J2 f+ m1 @: w            if(count==n_m[0]-1)
3 [/ H  s* E& H2 V0 G0 i4 Z4 |            {
  C) f! m4 o  }. C0 C6 p9 W. Z9 _6 t                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
  t) {) {% r- w8 a) Z7 j                  printf("%c",temp[f]);
1 [6 j& A% N# ~& i' Z                 printf("\n");
) V9 R3 _2 W. V5 E+ C6 A            }
0 @  S2 I' Q) M9 v            else
               printf("Sorted sequence cannot be determined.\n");
0 e* _$ {1 i9 R: Z* S        }
    }
    }
}
" ?, s; I" E6 _: g9 X. E1 h* O
) k' n4 a% E, ^9 x
& [$ M( @' J' B

1 A' ]0 F4 p0 T8 C
/ z$ L2 j. J5 R. Y* t. x* _8 x. s
1 E4 D3 p: Q4 ~
) l- R  x+ D/ W* u9 Z4 n/ R

来源：编程爱好者acm题库