编程竞赛题目（一）

厚积薄发

8 |8 d6 O" l, n5 ?( J  b% n
2 k' V( R7 ]1 v2 _1 cSorting 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.
% G( L1 B$ P, V: D% l0 aInput

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
" y9 n3 a9 @. J- z0 b. d
; K* D. G7 ^$ w: wFor each problem instance, output consists of one line. This line should be one of the following three:

' ]& M0 w1 s! ^% M* ?" RSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
6 I# _2 u! X8 f; G  m
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.

输入样例

4 6
3 E; Z' J7 W, d9 X5 ~4 z" B0 ^A<B
A<C
B<C
' r2 C7 `" t/ e$ xC<D
B<D
9 p( |4 `' \7 A, o' ~* O2 PA<B
8 a; c+ ]6 b, x) T" J1 l3 2
: R/ m+ X: n7 u) a7 L9 J) R  J$ VA<B
  p9 X- y8 p1 NB<A
/ D/ {+ F$ B7 i26 1
- q8 r2 Z" z# ~" Z  U5 BA<Z
0 0
- U- H5 }8 r2 h0 ?

! n) ]! }  O1 R  R( J* I输出样例

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source
& a; Q& b& Z3 k. F( o- q9 d
East Central North America 2001

# g  g- T8 X, n, \4 C9 t! A

程序解题1：

//By Jackie Cheung
7 p& k1 `& B" C9 O: q7 M#include <iostream>
. S7 G+ W. {+ a) g4 j7 t#include <string>
#include <cassert>
: J" T8 i9 a: f; [0 Htypedef  struct tagNODE
. I1 D% O  {, P: F* c" }{
6 M+ E- \9 z5 y8 j5 V$ W+ ]& f2 d    char val;
  ?/ w/ Y1 ?8 V) ]7 e9 ?9 s    struct tagNODE* link;
}NODE;
using namespace std;
" Y; X, j6 \$ Q7 s/ ^void Marshall(bool** arrary,int n)
{
4 D3 ^8 s$ d5 U4 x7 W; W# ]    for(int i=0;i<n;i++)
    {
: y: G5 r- I! s' Z        for (int j=0;j<n;j++)
. ~4 Y. I  _% L$ t& q; p+ }        {
6 M  `+ [- p+ \$ ?            if(true==arrary[j])
2 X5 g; C3 a2 `                for (int k=0;k<n;k++)
; H, J! d$ a+ l0 M                {
' V" F6 l4 J- y) N8 D. h% x  k8 Q                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
* ^: u3 k3 b! s+ x/ b' r        }
. Y4 A5 R) h+ L% f$ k$ _    }
};
8 ]5 G* p' L1 R% k8 v9 Obool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
3 }0 y2 }3 j1 @: d- N# R7 ~    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
. R8 U) b0 \" C* S5 w    if(1==nLeft)
# d$ H1 A  j2 _' `$ i    {
        Seq[n]='\0';
& m  Z: c! F/ J2 ]0 H6 p        return true;
* b6 S9 F) |$ R8 @, d( V' s4 X( q/ [    }
    for (int i=0;i<n;i++)
2 \; E' y6 F. r% Y/ h& b    {
" z- s0 \9 I% f6 P        if(true==array[nIndex])
        {
            
3 I: w& `8 R$ }' P4 P3 G            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
+ J: ~/ A, T# s. q  f) z1 q: L        }
0 j+ j1 J3 \2 D: P1 ?        if(true==bFlag)
6 m8 u. T4 C) C# [9 n" V9 r            return true;
    }
9 Z* Y" d  E+ O* V, g9 }) D    return false;
};
int main()
- o% n: t/ V3 D5 O# Q$ N{
    int nSeqLen;
$ H: s* t" C2 V    int nRelNum;
# ~& e" `2 w. T: z    cout<<"Input the length of the sequence:"<<endl;
% i' G, c& z7 n4 G1 V" S8 s8 t( B    cin>>nSeqLen;
) ~" |* w2 ^0 y& c    cout<<"Input the number of relations between the elements:"<<endl;
% U% x, ^* v5 d3 r/ O1 a& X    cin>>nRelNum;
3 f1 C, A. n8 p5 j3 J& R6 D) v    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
8 R- _. l/ G$ |6 W    if(nRelNum<nSeqLen-1)
    {
        cout<<"The relation can not be determined!"<<endl;
        return 0;
0 j& [4 O0 s8 g( g+ \# b* j3 \, W    }
    string* strRelations=new string[nRelNum];
* A2 B0 }5 j0 |! I8 V1 _    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

1 l' |# u8 e6 F# y# r0 T) p    for(int i=0;i<nRelNum;i++)
1 m* u& s% ^+ P( X- L8 ~8 N    {
0 a' P, F. p5 f  k        cout<<"Input the "<<i+1<<"th relation:"<<endl;
( ?- P5 J8 S# ^0 h7 s# D        cin>>strRelations;
4 I2 v. L0 e% `    }
% @. L% g; z8 Y5 u) J* s   
    for (int i=0;i<nSeqLen;i++)
    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
9 M- W! o; \: }5 `$ H    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
9 S) e) h( `' m% l8 D3 {# }    {
. s$ _2 A1 z5 W' w$ |$ e# c( V        char a=strRelations[0];
& D- y8 B, h6 [$ t$ D        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
; B! w6 y+ a8 a: |# ]+ @        array[a-'a'][b-'a']=true;
0 U/ D" \3 k& m0 J) E0 a
6 k' L2 G1 D0 O4 Q        Marshall(array,nSeqLen);

2 d9 }9 H3 C% n        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
% b# h! Z+ ]1 ~3 Y, f: |( F0 k9 H! ]            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
! A  d/ m5 n; C% F% R, N7 l                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
4 U$ P* l( y: ?                        delete []array[k];
                    delete []array;
2 \% K2 h) Q1 ]6 f7 l4 v                    delete []Seq;
                    return 0;

1 k! {0 q. x: Y# I$ B6 @/ x4 k. x            }
        }

        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
6 g' y5 ^  _# Y9 B" E6 E8 y                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
, {! J* G( f- M, W$ U. I                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
  x. d; J! _8 I                delete []array;
& B) |( K, X  b1 c: Z' c                delete []Seq;
                return 0;
) K, _4 f% f+ Z; p* U7 u            }
        }
4 u  u0 m! u0 y

    }
+ f3 z* h+ h5 [5 z8 H    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
- l+ n% C5 ?5 |    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
! t+ c; V) `) l5 z0 y, n/ |. \  b    delete []array;
    delete []Seq;
, N+ n! y, ^& r7 w0 g8 N) s   
3 B' q4 s% A3 i) ?) z7 \; K    return 0;
" R. ^, ?6 Y! `% x  B& J7 ^}

' ^; `  v" d  H) K/ @8 s& T程序解题二：#include"stdio.h"
+ s5 S; l( T  s# L$ gvoid main()
# ^, ]' _. _9 @6 w! `3 G/ n{
4 f8 r8 K& w2 r* u, x. c    int n_m[100][2];
    char re[1000][3],
    temp[26];
4 w4 T: z" X; p6 _    int i=0,j=0;
3 K. w; E8 f, d: j  }    scanf("%d%d",&n_m[0],&n_m[1]);
  i6 R9 j9 x/ L5 e+ ]  j2 o' l    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
, z# v. i( r. V9 ]4 H    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
* s( H; _/ E4 `- m$ }9 C   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
4 u/ O& w3 U+ t; U2 B       int a=0,b=0,l=1;
9 a& s) u7 T" h) h5 S+ j7 D       for(a=j;a<j+n_m[1]-1;a++)
& F$ S/ f. Y& d3 z1 y+ P+ m         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])
' j7 O& x& P+ G6 A( y0 V            {
            l=0;
1 _. ^/ J' @6 F, p2 `( r3 F            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
/ I# F  l: Q4 E' [8 m         }
5 [# {4 }$ g# L4 `) \  K      if(l==0)
( U6 `$ x0 J. i  V: v" M          continue;//Inconsistency found after x relations.
    else{
' Z7 x- d$ s- p2 a+ v$ b+ N2 Y: `           if(n_m[1]<n_m[0]-1)
1 f1 P1 y& ~% I( @1 W        {
" G- h5 T1 l+ `  B" ~            printf("Sorted sequence cannot be determined.\n");
) I2 T, o; H! X6 `            l=0;
: M) c/ P; t- ^8 m, g        }
8 C3 c6 t7 b  F% S        else
) s& c4 @, E# \2 x& }        {
( T! N, q" W' \# M9 B: A          if(n_m[1]==n_m[0]-1)
7 Q$ U+ O2 M: A) @9 t7 T          {   
              int k=0,p=0;
  m: _8 F2 x6 D) |/ J              for( ;k<n_m[1]-1;k++)
* v6 T7 n. N, P; l9 x                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
+ O- @, `: p2 R) Y( ]$ N5 P* r8 q                      {
                      printf("Sorted sequence cannot be determined.\n");
( \4 z" z+ q2 f                      break;
                      l=0;
                      }
! G! `  I9 }5 Q  f- f          }
        }
1 m* {) z- K7 f5 ~        if(l==0)
        continue;//Sorted sequence cannot be determined.
' t" ^; ?3 h$ r& a: {; E
        else
% u) B4 ?1 O% k         {
           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
- W$ j9 n: N1 A, K5 F; {# B              {
! t% D! S; S" B+ Z                char t3=temp[t1];
                temp[t1]=temp[t2];
+ m* k# ^. @7 V9 Q; B                temp[t2]=t3;
) L. q5 V) E/ Y/ ~/ x              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
$ o9 Q4 b6 ^5 M0 U& J% P            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
1 C) i/ Q2 c) @7 y            }
% D# T# l1 i0 b            if(count==n_m[0]-1)
3 E: ^& ^( T- I            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
  u" w0 d6 K' M                  printf("%c",temp[f]);
4 n  p8 N5 g+ T; j2 ?9 _6 @                 printf("\n");
7 @4 b4 z+ [) E, B& T            }
. N; k* D0 V2 u$ ?) q            else
0 W9 s+ V* H. Y3 G5 p               printf("Sorted sequence cannot be determined.\n");
, k4 R, j2 Y  [' S* y' e        }
    }
: U: D! U0 @* ^: q    }
" K" s0 C' S( Y7 t- ~0 F% W}
) q  R* n3 q8 {' Q+ e7 o8 w2 z
$ \. l% u# N6 ?* p- ^3 ^
% y6 ~: Z3 p6 C0 b5 r
" k$ D8 w6 a8 `9 t7 w' K

9 ^6 q9 p0 m2 k' g) M) n8 G
. K, d' j3 f+ f0 z! [
" Z. f- T7 B# ^$ d$ ~
0 ^8 v, M# F3 H4 X" ~7 l8 q

来源：编程爱好者acm题库