编程竞赛题目（一）

厚积薄发

, R2 V+ L4 R3 W" U# g, Y
Sorting It All OutDescription

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.
Output
9 T- C8 {9 \6 Y+ X% t  ^5 |7 L2 U9 c
7 h3 M- o4 O0 i; n5 m2 ^3 o: wFor 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 L8 [8 O- ~& y) E( y( d2 K6 JSorted sequence cannot be determined.
Inconsistency found after ** relations.

3 h. \9 N* h1 t  u6 G5 J6 }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.
8 `$ q0 Q; V- d+ n; k  c; K
输入样例

3 b+ j% o/ z! W1 I6 x/ J4 6
7 l2 w( r+ M3 m, V4 s! HA<B
3 G# x# ]! O; wA<C
* }  ~  `9 V8 UB<C
0 o6 b/ p7 T! b' R( s9 `7 Q9 RC<D
8 ~7 ^2 y9 P# WB<D
A<B
3 2
A<B
( w% X* \; K# t' |! h. RB<A
) w. {/ }4 a2 q) @: m, z! q26 1
. v. [2 n* w; cA<Z
& ~6 O- y2 M: D' H0 n+ v0 0

输出样例

/ V4 n; t7 n! A1 M8 A) M" OSorted sequence determined after 4 relations: ABCD.
7 [5 q/ G9 F4 j; xInconsistency found after 2 relations.
+ b( U( a7 \* ~7 cSorted sequence cannot be determined.

Source

East Central North America 2001

2 \. q# G% L& p8 p8 ~

程序解题1：

$ z+ s$ i2 {6 ]" t) ^" e//By Jackie Cheung
#include <iostream>
#include <string>
0 i- d' M. ^; A5 ~#include <cassert>
/ S9 M; P/ V. k0 v9 j' ?typedef  struct tagNODE
* p- e; J& ]! X) b{
    char val;
    struct tagNODE* link;
0 K  Z* l9 W( m7 x1 {}NODE;
# C  y2 `: V+ @( ?6 iusing namespace std;
void Marshall(bool** arrary,int n)
{
1 d+ u6 O& x# L0 J6 R    for(int i=0;i<n;i++)
    {
4 N2 M; h3 m- g+ x! b% q        for (int j=0;j<n;j++)
1 ]/ h" ^( e0 M        {
# J4 j6 b/ b5 p1 O            if(true==arrary[j])
                for (int k=0;k<n;k++)
9 t8 _8 D/ [1 W( l" J                {
: ~* t* G$ d1 ^% A. X% K% ^$ [6 i                    arrary[j][k]=arrary[j][k] || arrary[k];
  X8 U* v: d/ Z3 o& g                }
        }
    }
};
' _, M& s6 U! Obool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
' A; C& s# a" {: V# t{
4 a; u# \$ J9 j& S9 S9 K: U- N7 ]    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
* h9 G/ q) d8 G! a0 L    {
        Seq[n]='\0';
        return true;
    }
+ x; v' C6 o4 R" F3 z- s) S# a    for (int i=0;i<n;i++)
7 O; r! A2 A$ {0 `* X+ ]# {    {
( M. @$ \: D" W& g        if(true==array[nIndex])
, p. G2 H' R2 Q$ k+ g( ^6 ?) F        {
9 v3 H8 f% Q( ?            
1 p' _4 O( m* M2 W            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
* F$ A1 q" L1 `6 ?6 z/ n! X        }
        if(true==bFlag)
            return true;
    }
    return false;
8 Q0 Z: m+ R" F# X};
# n6 K, T- o0 l: rint main()
1 ?1 g0 y6 |7 \0 C& ]{
    int nSeqLen;
, @! J( ?0 U7 V# N    int nRelNum;
* r* u8 e" Y/ @1 I, k- d4 f3 z    cout<<"Input the length of the sequence:"<<endl;
# ~% M" Y" z* }- {" \2 ^6 Q7 w    cin>>nSeqLen;
8 J  d8 N& k# g& G+ T    cout<<"Input the number of relations between the elements:"<<endl;
; v: R* t8 N  [0 x5 l    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
4 [% T# L) k5 [, ?# {$ }" X    {
1 V( o# s& r. w# k: [/ d        cout<<"The relation can not be determined!"<<endl;
, V' r$ n0 }2 C4 o        return 0;
    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
: U6 W! C2 @* O7 E- x( W: ^    bool** array=new bool*[nSeqLen];
$ x% _" c' }: e* t2 k0 o* k  A
    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
0 O5 s, _1 u& D9 R7 i0 `        cin>>strRelations;
3 @1 ], x' E3 \& n    }
+ c# V3 ]  B5 a$ _- o7 J8 @$ f   
. e* @0 i/ v+ G. E; }    for (int i=0;i<nSeqLen;i++)
    {
8 q  ^' r6 x% E; A        array=new bool[nSeqLen];
- Q) p; y0 w1 T9 V3 D        for (int j=0;j<nSeqLen;j++)
- x5 N% m& n! Z7 ]& w0 z6 T            array[j]=false;
1 F% P  M9 A" E  A6 t$ R    }
# N6 S# Z1 y7 c+ k! Q    //The main loop
9 Q$ q& W5 D* A0 V6 r    for (int i=0;i<nRelNum;i++)
    {
        char a=strRelations[0];
: \" f, D- B1 D        char b=strRelations[2];
  j! W5 P5 d+ G3 k* S        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
( y7 \7 g& m6 L2 g7 K$ J) @2 ~        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);
/ D. k, K7 D3 `; l3 f" y# A0 ~
        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
" W) B2 V5 t4 u2 b! ~            if(true==array[m][m])
            {
9 k: v& l% d' n4 m' c                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
! G5 v8 z( t: A. E- W6 q) d                        delete []array[k];
                    delete []array;
7 R7 w# Q4 Z8 i5 R2 q/ K  c# u                    delete []Seq;
                    return 0;
8 e# i+ ]7 ^& ]
3 u! t7 \4 ^# J            }
        }
8 G% @' ]. D1 n( }/ L6 Y+ R/ T9 {
        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
+ S- c2 R5 l6 d' q/ X            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
; W; G8 R6 b$ C7 I3 K8 f- k                    delete []array[m];
                delete []array;
' |) j2 _# t8 p0 @6 O" I8 g                delete []Seq;
* g* R) |0 q; v- U' Z                return 0;
0 ~2 t5 \0 m& x: x            }
/ ~- O1 j) h1 W' ]6 N7 n        }


6 f, g8 N: ]9 `( U    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
# X2 h5 c0 |% }4 o$ p- n    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
    delete []Seq;
   
& ~- I( S  o5 l. }% Z    return 0;
}
' {# d( s, A3 V  T4 [, K
程序解题二：#include"stdio.h"
9 @9 w8 I6 j  m* Vvoid main()
{
    int n_m[100][2];
# L' \/ O1 \, N- Y    char re[1000][3],
    temp[26];
& m6 t% D( o% ?& H. e; V  q' j) t    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
, o1 a# c7 c- M5 L; }4 h- I& M% }    while(n_m[0]!=0&&n_m[1]!=0)
    {
* X# g! A3 R  h3 @8 E    i++;
4 s, b7 r$ s+ e- h7 Q4 Z/ Y$ n    scanf("%d%d",&n_m[0],&n_m[1]);
: m9 c' J$ p% u8 a    for( int f=0;f<n_m[1];f++,j++)
1 C7 T1 Z$ H, n7 @    scanf("%s",&re[j]);
    }
    i=0;
5 n' g. V+ g0 U1 o6 {7 H8 f    j=0;
# V3 V4 ]3 k  A5 S, x; _2 m   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++)
         for(b=a+1;b<j+n_m[1];b++)
9 X4 l3 T4 S# ^* y         {
              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])
            {
# b. ]& C9 [/ o! M$ Q$ M+ y8 f            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
, d2 c- B4 u; g$ i0 m! Y. D            break;
            }
# }; o; _* _  h) A* ?         }
# o& ?9 Q. P2 y& f: S- C+ m      if(l==0)
5 T7 h& s; J+ {, X5 }          continue;//Inconsistency found after x relations.
+ q- w! i" U! l% M    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
3 J: P7 ]5 i8 e9 r. M3 ]% W7 q            l=0;
3 ^. m7 u5 F4 u  ]$ \        }
        else
        {
3 L: b5 B. E. q) ]; f6 M4 W! x) b          if(n_m[1]==n_m[0]-1)
3 T3 r- M, f$ ^* ]2 A4 B# I# i          {   
              int k=0,p=0;
$ m( p0 M& W( I/ O7 r. H              for( ;k<n_m[1]-1;k++)
! b( \8 o# y* A+ r" t/ _                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
) O% T% Q# j7 |' R& w6 K                      break;
                      l=0;
$ S' q! b+ P7 J                      }
          }
        }
% s% ?- o( n* ?( B6 F        if(l==0)
$ C: D% g, E3 v% B* _' k  @        continue;//Sorted sequence cannot be determined.
+ W6 f4 f- G- J8 D( s  T
        else
         {
           
0 I) g. q2 ^- [, S0 ~            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
8 z# ~, Z  T; m- m            for(k=0;k<n_m[1];k++,j++)
" r1 h2 P  G& [, J' U) ?            {
% s3 g) ?, O  `: G- @" A' q" `                int t1=0,t2=0;
2 s& }* ~- I  i  p* w              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
3 j0 M9 p/ U) }+ ?) e                   t1=s;
                      if(temp==re[2])
2 ?7 b* _# w2 u( b                   t2=s;
4 W7 F9 y1 c6 }! l2 O" K+ `5 {              }
& Z+ c0 c% E7 L( c              if((t1>t2)&&re[1]=='<')
              {
$ r" Y2 s4 J6 O8 _8 l2 n- B: a                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
9 ~* W) [; Z7 X9 f              }
) r) c- o4 q3 X- K" R/ ^$ M7 J3 h. K% L            }
        int count=0;
        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])
; e7 }& p9 n1 q% {            {
                count++;
                break;
5 E* T  @& R  S: B            }
& |6 ~4 B* L6 |5 u) A            if(count==n_m[0]-1)
+ d" r: v2 u, y7 F3 ^            {
: t" y% I( b5 ?$ ~' M                printf("Sorted sequence determined after %d relations:",n_m[1]);
1 W: \7 W. Y! D2 `                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
. H0 h* r5 N; z/ R) G& u+ S- H) x3 p' ]                 printf("\n");
            }
+ j+ r9 [, Y' y- f% Q            else
               printf("Sorted sequence cannot be determined.\n");
        }
% \; S& f, Q* F    }
    }
}
! w$ t( U7 V- ]* i! i0 |0 z
, u$ ]5 Z8 s4 V; Z+ N; x1 M
) D7 n8 w, F! C; o3 t

7 A' w" c# G( }+ h, H1 [

5 `$ n9 L, H& |) ?

来源：编程爱好者acm题库