编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription

  T8 u# j0 g' o; t/ E1 }: j3 qAn 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

$ M& W3 @. Z3 HInput 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 j  T1 W" M# _0 POutput

: U& j  Z- L( X$ L* g8 S2 b! W0 RFor each problem instance, output consists of one line. This line should be one of the following three:
) \$ i$ V- ]8 |6 w& D2 ]# ?
1 q$ [! n/ y1 _1 q6 n4 HSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
% ~8 c3 V2 C" M1 J: i
/ R9 T/ R9 ~7 t: ywhere ** 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.

' T5 `+ U: R; u输入样例

  R  A1 S$ m8 G3 d+ W- z3 n4 6
A<B
A<C
. W( ~( W  B9 ?- D2 UB<C
8 o* T# N% O5 F- f1 o) U& U: hC<D
  s9 h: B/ |  mB<D
/ w5 k3 D: Z  G) l2 V: y, FA<B
3 2
1 [5 f1 c# I& x7 G9 M5 M5 h9 OA<B
9 ?9 G' C8 @+ ?& `% QB<A
& h  V1 O$ z7 g0 V* V26 1
A<Z
0 0
" D8 r8 R* U' V9 j2 \- \6 ?

, Z# [1 j* v4 {5 S输出样例

; w0 F: [) O4 |& FSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
7 Z# @8 s3 t; c6 oSorted sequence cannot be determined.

Source

2 x5 d0 v0 f* M" pEast Central North America 2001

2 x, A( j; k2 A. \  I

程序解题1：

3 m% C) B; i9 u  W. u3 k: n//By Jackie Cheung
#include <iostream>
/ h  @$ z5 w( S* _; ]#include <string>
% ]; E) t+ t+ Y6 Q" ?% W#include <cassert>
$ d, ^! S% [3 T- |" ^8 Y$ Otypedef  struct tagNODE
) D& l! O) n* Z{
    char val;
" l& o, q' i9 m9 ]. E4 q    struct tagNODE* link;
}NODE;
" P% j2 E/ g% f7 c5 I" ]using namespace std;
void Marshall(bool** arrary,int n)
{
! t2 E5 q) a/ u* i$ N% e. W+ w    for(int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
* k" I/ F) K: z  L$ e$ J  U8 U; o        {
: B! B# x% G% t! E& a0 Q9 H% v            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
8 M& H2 y6 H7 _9 `% E$ e                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
0 r. N9 R) C0 N7 _9 G! z/ M    }
( p: k) ?) J' r; K$ W; ~& m};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
5 c2 O+ D. u! ~. m+ p9 n4 i{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
3 H+ {2 d# w2 V3 Z- }    if(1==nLeft)
    {
        Seq[n]='\0';
2 q9 I+ O4 ~1 g- m+ V" h  Q        return true;
    }
, [$ F: h. @7 c# X0 }9 s8 d6 Z' X7 R/ y    for (int i=0;i<n;i++)
' M# o; F" a: ]1 t! M; t    {
        if(true==array[nIndex])
        {
! H# Z+ |: x) J5 f) b            
. [7 U+ L! q; S" c. x, j            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
" P9 e% ]1 X; [    }
    return false;
};
int main()
{
2 F; T9 I6 S7 l# y    int nSeqLen;
1 z1 @% o- X7 D7 \$ L! t  I    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
/ D; s. t- f6 h6 @( J5 a0 F    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
4 @1 Y; u2 o8 N) a7 V& b" t3 x    if(nRelNum<nSeqLen-1)
) F# f) [! D: K; u6 {( s6 L4 H" H. D    {
4 v1 i9 t+ G* c        cout<<"The relation can not be determined!"<<endl;
, ~3 ]0 i: c7 }  ?; c9 o        return 0;
    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
5 L5 [5 h7 n8 w2 i; ?    bool** array=new bool*[nSeqLen];
. U# a  r% W5 ?; S2 e2 @% N0 [% ^9 j
    for(int i=0;i<nRelNum;i++)
    {
5 ]2 n" \! M2 @1 i3 `& S        cout<<"Input the "<<i+1<<"th relation:"<<endl;
; _7 ?& y! k# e9 r' A. X        cin>>strRelations;
    }
   
    for (int i=0;i<nSeqLen;i++)
5 U& `( h5 K: g    {
9 E* n, ^1 T. r% K% t/ W/ j        array=new bool[nSeqLen];
& X2 u; m, V! V( x( s7 Y# t3 @7 a8 F5 n        for (int j=0;j<nSeqLen;j++)
" z/ W; Y) I3 C6 |) `            array[j]=false;
9 V& M5 w6 d( y9 O/ }    }
    //The main loop
% |4 a* a' l% M9 k) B    for (int i=0;i<nRelNum;i++)
    {
        char a=strRelations[0];
        char b=strRelations[2];
  l4 Q9 I" F) _/ J        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
4 L9 m0 C8 ~0 _$ A' M9 e
! Q6 ]& P( W  C0 X        Marshall(array,nSeqLen);

: p: d3 A2 }; l0 }# @$ c        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
: y6 X0 g/ w+ G        {
% V& U8 `, Q* b/ T9 N" A2 q            if(true==array[m][m])
' h2 Z$ O, O' s$ T; _            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
- V; L# @" m4 K) j5 i* V                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
5 k- U8 z$ U& T) }. k6 Z/ h                        delete []array[k];
& w7 A: o& r3 [" T' l/ f) M- a                    delete []array;
                    delete []Seq;
                    return 0;
- e; E; [  m+ Z$ Y1 F
            }
3 s% h# v) T' j& Q: _% G        }

        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
. g' T) d+ V! E! \* f' h! r! s4 x            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
/ p& V4 m5 f( |' G; O            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
                delete []Seq;
                return 0;
            }
4 W( ?% I$ O4 Q& Z+ h        }
. k- t2 B& U; u% B( R
" F3 _  R9 ]4 ?$ Q0 v
    }
  t) r8 a! O( F8 z6 F; _    //If the program has come to here ,then the relationship hasn't been determined!!!
/ |9 n7 }. c. u+ h0 n+ q/ S" A$ u3 h    cout<<"The relation can not be determined!"<<endl;
0 L1 f% z7 q8 q( W    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
& q9 s* m/ n" z8 N  X    delete []Seq;
3 B5 q9 Y# X) A4 u: p   
7 z' ^! D& H/ I! h. p- X8 E    return 0;
, j, `" h9 Q8 B7 y: H( e}

程序解题二：#include"stdio.h"
void main()
{
4 _( K2 T: a- L5 \$ V) n' j1 \, O    int n_m[100][2];
: z' v1 `+ j# A% [7 x3 u3 _    char re[1000][3],
    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
" A2 O% c7 k' D4 _- `8 G    for( ;j<n_m[1];j++)
4 U' E/ d% A3 L& f9 i    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
. t& r/ ?$ N) H; \  S! C8 ]) K    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
8 s$ s5 S$ k5 y* ?+ M    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
3 s+ H/ W" U& @5 D  G  Y   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++)
, R) Y  h0 l* C         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])
            {
$ n2 e4 B, e8 O            l=0;
- h2 D* b. ]: i# H$ Q8 i. P3 h            printf("Inconsistency found after %d relations.\n",n_m[1]);
2 L2 k  f; `7 G! M            break;
            }
' F0 ~  k1 [' z: N         }
5 M; f7 p7 O1 V# W) P      if(l==0)
6 H: Z! g, d4 W6 {          continue;//Inconsistency found after x relations.
    else{
; L( ~; h5 H- t! Y+ w           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
1 y3 {2 V+ W# E" ~( }" {            l=0;
        }
        else
        {
          if(n_m[1]==n_m[0]-1)
, p' C! t4 g5 h% f, t" B: e' r          {   
, d# u. }9 ^- K$ T: p8 t& ?  M0 I7 O              int k=0,p=0;
/ ~8 Q  u. _% O9 Y: B3 ]5 Z- {) J              for( ;k<n_m[1]-1;k++)
9 M) q4 E  C- E, \                  for(p=k+1;p<n_m[1];p++)
& P% X$ ?3 [/ S" J' ?% b) ]                      if(re[0]==re[0]||re[2]==re[2])
% O0 o/ s/ K$ }. F" u" d                      {
/ k  j7 j4 m& ]                      printf("Sorted sequence cannot be determined.\n");
0 P* b8 l- i* V7 s: i. y                      break;
. Y% R! I6 [1 N9 t9 R2 D                      l=0;
. z0 Y  V% c+ {, z7 A+ x; u, E                      }
5 k6 i5 c' @! Z          }
9 k9 N' p! f7 ~4 t. o        }
        if(l==0)
0 E! y7 W5 c7 s: r5 j, s        continue;//Sorted sequence cannot be determined.

        else
         {
           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
0 V% y: z& j' r0 u% U/ |/ ~            for(k=0;k<n_m[1];k++,j++)
, P+ C, F; o' A! Z$ I# {            {
                int t1=0,t2=0;
6 t3 y8 {7 V. A+ c6 A2 ?              for(int s=0;s<n_m[0];s++)
. w$ G2 b3 j4 t0 z$ c              {
               if(temp==re[0])
, E  I7 W4 ^3 M$ S                   t1=s;
                      if(temp==re[2])
6 `, q$ q( l/ K9 s# U                   t2=s;
$ k: M- u, {# t: L8 w& x              }
              if((t1>t2)&&re[1]=='<')
              {
& A& ~+ o2 x# y                char t3=temp[t1];
2 ]& J" R+ d$ H9 M* H                temp[t1]=temp[t2];
, @* z( ^0 Q" B8 z" m: ?                temp[t2]=t3;
; V1 X& F7 Y# g; `; ~5 O              }
            }
0 X0 R& N* ^- y# j7 D7 B3 p        int count=0;
3 l" g1 `8 q* P+ W' _        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])
2 Y- L. G( a  I1 \4 [7 n            {
                count++;
1 O" ?; ~" D0 t# Y) M                break;
            }
            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++)
                  printf("%c",temp[f]);
                 printf("\n");
$ n8 a+ ~  H- h, r/ J            }
            else
- X& ~) Q' y; A, C! h6 N7 I8 C               printf("Sorted sequence cannot be determined.\n");
        }
    }
    }
}

( v3 X) |' T, H( L/ y. f; C- X
* d! \" Q7 S! `/ \4 W& w5 [3 Z  r# B

5 s9 c4 h4 U: k4 b

: y7 G8 b' I  R) C  ^
' q' D% j: Q- N' H) \7 c/ ]6 P% M
3 |3 N1 p0 H3 j' O3 a

来源：编程爱好者acm题库