编程竞赛题目（一）

厚积薄发

2 |5 t  R& ^2 ~" T6 s
Sorting It All OutDescription
) I- m5 @5 w# {
( |* b8 f1 G, Q) yAn 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.
$ Q* y$ i0 k* C9 A. j" Z1 t( j! gInput

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.
7 u! _* G. C# p% ?/ [& IOutput

8 ?8 {) X9 l# R; K* JFor 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 N% h  S4 b3 z# W; G& C* }Sorted sequence cannot be determined.
) a, G7 `' U# Z% u6 |4 gInconsistency found after ** relations.
) Z9 W. }2 S9 N5 n$ R
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.
/ x( X7 ~# F( A
9 }2 C4 N2 b6 }- H: B输入样例

; z. S) e. C6 n# Z" H6 q; s4 6
A<B
- g. X8 j, ^. y9 ?' dA<C
, L; Q( o' |8 h! w8 K" w& }- ]B<C
% x3 |5 Y& j. A0 ~" o8 F$ D/ A0 M% AC<D
' o/ z: h" C7 ^$ L" M5 X0 EB<D
# M8 s. @3 J7 a) q/ [- VA<B
1 i5 q3 r" q& P& v' A/ O7 t3 2
A<B
B<A
! x, N1 E( c2 y9 S+ u26 1
A<Z
0 0

输出样例

& a, @- z( `/ |, f: z1 V) ASorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
7 L( E2 Y$ W% A! wSorted sequence cannot be determined.

Source
$ x" ]/ ~" x  Q4 U/ o
East Central North America 2001

* p9 L% c" |$ R, X$ R& u

程序解题1：

//By Jackie Cheung
1 c2 U% D& `# G+ E! z5 b#include <iostream>
#include <string>
7 v" M0 g/ C0 g$ U#include <cassert>
  y7 u  B' H5 C6 p8 A3 ^3 Itypedef  struct tagNODE
- N0 p: [. z/ N; C$ }# V3 F7 B{
    char val;
    struct tagNODE* link;
' ]% l$ Z: ^" f9 U8 T) Q}NODE;
% _4 y1 t5 g" [7 t: v% J* Vusing namespace std;
void Marshall(bool** arrary,int n)
{
7 c* g& }* w& C    for(int i=0;i<n;i++)
3 ~% ^5 A3 h1 m+ c; @" R    {
        for (int j=0;j<n;j++)
        {
6 V" l! P! c3 R            if(true==arrary[j])
                for (int k=0;k<n;k++)
8 I& E, `# X' u4 U- b3 @' I4 t: {$ {                {
3 i( p1 }% D) h8 N; v/ w" P6 K8 T                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
! A) {6 F6 F1 w2 G2 R/ x; v    }
' c6 j' ^! }6 R};
8 `' D, Z! \) I. qbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
1 Y+ z4 f3 B; B9 ~% P3 t' _& o    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
# L8 t4 ^9 H. E8 L  `    bool bFlag=false;
    if(1==nLeft)
% U$ G, n) Y1 t$ k8 u: K1 T6 w    {
        Seq[n]='\0';
        return true;
    }
    for (int i=0;i<n;i++)
7 Z, F6 s8 I. s5 ]( |  Q0 k    {
6 ~9 R9 ]9 x+ H/ k        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
0 F- a2 b* K0 }$ U& N# o6 [/ S( ^        }
        if(true==bFlag)
            return true;
7 z, |; i; K, U; J& c    }
    return false;
; Z3 \. K9 j/ ]4 g! k4 W8 s};
int main()
  F! m+ v7 x3 g$ `% W& z{
    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
6 w. ~4 L( }6 w; D0 e6 V& W    cin>>nRelNum;
$ z6 C$ u( f' A* r8 D; ~( U3 r    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
2 t" N" U+ z: O5 D! h4 u9 m% _    if(nRelNum<nSeqLen-1)
    {
        cout<<"The relation can not be determined!"<<endl;
        return 0;
5 ^2 L4 a, A8 d& F$ ~4 M    }
    string* strRelations=new string[nRelNum];
& T4 m- C/ x- ~: v2 g: |+ S) s# D& E    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
    {
+ R! o* P' a+ x+ O4 ?6 @/ a        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
   
    for (int i=0;i<nSeqLen;i++)
5 r; `/ X3 e) ?! e5 R- j5 q; d4 i    {
( e, _9 v. V, V! m$ `$ H        array=new bool[nSeqLen];
1 b4 V$ H" D0 g9 b+ n        for (int j=0;j<nSeqLen;j++)
8 N$ u; {. z& @            array[j]=false;
) B1 j! V/ E# M3 N! Z& F    }
    //The main loop
' I% F4 Z9 U* J0 n6 D    for (int i=0;i<nRelNum;i++)
    {
! z3 x9 z: K$ O" L" ^        char a=strRelations[0];
' c; p+ ~) l" u; k        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
1 S* e$ C8 M1 R& p        array[a-'a'][b-'a']=true;
( X/ }0 Y- F' \3 s+ Z
        Marshall(array,nSeqLen);

$ F) j9 L; o* g, X4 t/ T+ D9 {        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
0 {2 M  O- _2 p( h) {0 A                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
5 L3 N( e3 t/ ^7 i                        delete []array[k];
" T3 i0 f4 ~' e% x                    delete []array;
+ R! j# V& I: N1 X. P! o  C/ D0 ?# s+ x                    delete []Seq;
                    return 0;
& d' d( N! W# ?' t4 @5 }! e
% x; P8 w+ Z8 F, v, @            }
7 d$ Q1 t# l6 A, m6 N6 V" ]  w! z        }
1 ~/ A; c- V/ _& H7 G! M
        //Check for the determined sequence after  every relation   
2 i% h8 |  [% s: h( ~, A        for (int j=0;j<nSeqLen;j++)
; e. L+ c1 t2 \5 n* i' `9 q( Z( S        {
5 [& \  e& G$ C- k' i( D            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
) ^( f" @% Q# [. n: y( x2 w; p9 f                delete []array;
- X& \$ d3 b& b% e1 b( b                delete []Seq;
                return 0;
# T, ?; _% D9 Q( ?$ D            }
0 b1 L! q& O; V+ N+ f& w1 ?        }
1 |, W, ]  }4 S- Q
- O9 ?6 F; q) s6 n5 K5 {: E
    }
0 F3 R- A, r0 ^! r; Y: z  s% f    //If the program has come to here ,then the relationship hasn't been determined!!!
' L0 X% @0 m/ P1 c9 O: v0 G4 D* W% M' F    cout<<"The relation can not be determined!"<<endl;
% B. N8 E4 q' @  }) f4 e3 o* H    delete []strRelations;
# V& ]* ~6 k- l4 _. o' U: T: |    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
    delete []Seq;
1 i$ b- o# x7 T' u   
, p+ _, Z7 z- V5 ?- b    return 0;
}
& d6 Z) A9 u0 P  y+ U
程序解题二：#include"stdio.h"
void main()
{
# {) B, P" r( C9 T6 M" x    int n_m[100][2];
    char re[1000][3],
    temp[26];
6 I6 c$ E% T3 t1 I    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
: p2 a2 y* ]" T  T! C9 G: \3 |    for( ;j<n_m[1];j++)
) j* J# n2 V" H* k) U6 _3 e    scanf("%s",&re[j]);
3 H4 @1 Q/ a) @2 o( S/ N3 ~) y    while(n_m[0]!=0&&n_m[1]!=0)
    {
0 B& [. b' r4 C  {$ N2 {5 f6 J% O( x    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
$ L' |, C; u8 K" t2 ?+ Y    scanf("%s",&re[j]);
    }
    i=0;
/ l% V# X7 [) D' B" k    j=0;
3 C, {7 k5 i. e7 V   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
" c3 W7 e& K; I) ^7 g$ E    {
       int a=0,b=0,l=1;
       for(a=j;a<j+n_m[1]-1;a++)
- T/ ]7 Z$ C/ R; `2 I! p4 @         for(b=a+1;b<j+n_m[1];b++)
         {
( O! _5 n7 q: }              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])
            {
+ m2 D! `( h2 Y, K            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
5 n# {3 S- M* m. m* n' N         }
. q& H$ N& P' h1 r$ Y' N      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
        {
9 [6 x7 S' H. }6 f8 i5 ~5 |            printf("Sorted sequence cannot be determined.\n");
            l=0;
$ A( T8 M1 n3 y/ H& d        }
; l1 v% t  r6 o) e        else
        {
          if(n_m[1]==n_m[0]-1)
8 e2 f2 K: @! {6 m1 |* q7 i          {   
5 t9 M! }1 g( ]. q+ F$ k& `1 ^& T              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
% n8 E$ Z7 ^3 \- m: y4 E+ W1 u/ z                  for(p=k+1;p<n_m[1];p++)
9 |4 s8 }% @. J                      if(re[0]==re[0]||re[2]==re[2])
; ], h0 L$ ?/ q                      {
* G( E5 C; _0 Z% I8 f: a. u* _2 E                      printf("Sorted sequence cannot be determined.\n");
' K: p( b/ z6 t: t( y- e, i+ F                      break;
                      l=0;
0 t2 _" x( D' [6 [' u4 e                      }
          }
        }
* f% h0 e3 o7 a; m* G1 x& z4 F        if(l==0)
. m, S2 u  ^7 c) ]. O* K) M4 Z        continue;//Sorted sequence cannot be determined.

        else
2 h( i# @0 C4 Z0 v         {
           
9 T/ a6 s' r) l            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
  C! Z) {+ w; }  P# D+ J  b* a- N            for(k=0;k<n_m[1];k++,j++)
            {
, D  E4 R  i0 _, G5 Q# T                int t1=0,t2=0;
) a) B; F6 P, |, ?) L              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
* Y% `4 r4 o  i: y                   t1=s;
                      if(temp==re[2])
                   t2=s;
              }
6 `$ `$ R9 s9 A/ b              if((t1>t2)&&re[1]=='<')
              {
& A+ d0 F1 Y% j0 b, g                char t3=temp[t1];
, J+ z1 S. s. ~6 j% u4 B' X                temp[t1]=temp[t2];
                temp[t2]=t3;
: u' ?3 {5 R# [! @/ a4 h1 p) g; @              }
            }
# V7 q: E) \( P$ I; L- k/ [        int count=0;
' e% e. J5 ?. n+ ^4 _' Z5 N9 X7 t% j        for(int s=0;s<n_m[0]-1;s++)
2 u' s2 L2 D3 z        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
4 _$ e. X9 i0 k& b            {
                count++;
& R; z  Q; \5 Z, ^2 W                break;
0 V' Z/ [9 i% i            }
            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]);
  r& Y) D! A% v' u6 Q                 printf("\n");
% `& A  _, P$ M- E) l& n8 \            }
            else
8 V, ^" S& X. a# g& Z               printf("Sorted sequence cannot be determined.\n");
        }
) d; Z& v+ T  \    }
2 ]( F# u3 X$ i) z; Q    }
}

% k. v6 k; j( e& s) t* o5 P
! z/ \9 c6 m6 A7 Q# L$ v  L2 T



  J: r* v' O; B6 }8 ?
  Y  P/ M2 g3 W! c
4 I2 `2 I  Z7 m* y# a3 s

来源：编程爱好者acm题库