Posted on 2008-08-19 19:27
Hero 阅读(112)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
//Accepted 2003 C++ 00:00.46 1344K
//求出传递闭包后，a对应的密码的outdeg应该为(inn-1)，b->(inn-2)
//然后用pwd2word[]建立映射
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int size = 300 ;
int edge[size][size] ;
int indeg[size] ;
int outdeg[size] ;
int text2pwd[size] ;//文本到对应密码的转换
int pwd2text[size] ;//密码到对应文本的转换
char fword[300000] ; char sword[300000] ;
int flen = 0 ; int slen = 0 ;
int inn, inp, testnum ;
bool can = true ;
void input()
{
memset( edge, 0, sizeof(edge) ) ;
scanf( "%d %d", &inn, &inp ) ;
scanf( "%s", fword ) ;
for( int i=2; i<=inp; i++ ) {
scanf( "%s", sword ) ;
flen = strlen( fword ) ; slen = strlen( sword ) ;
int k = 0 ; for( k=0; fword[k]==sword[k]&&k<slen&&k<flen; k++ ) ;//找到第一个不相同的字母
if( k < flen && k < slen ) {
edge[fword[k]-'a'+1][sword[k]-'a'+1] = 1 ;//建图
}
strcpy( fword, sword ) ;
}
//scanf( "%s", fword ) ;//最恶心的数据输入(At the next line is encrypted message.)
getchar() ;//注意输入的一个text不是一个字符串
gets( fword ) ;//别忘了getchar() ;
}
void f_indeg()
{
memset( indeg, 0, sizeof(indeg) ) ;
for( int sn=1; sn<=inn; sn++ ) {
for( int en=1; en<=inn; en++ ) {
if( edge[en][sn] ) indeg[sn]++ ;
}
edge[sn][sn] = 0 ;
}//构建indeg[]入度
}
void f_outdeg()
{
memset( outdeg, 0, sizeof(outdeg) ) ;
for( int sn=1; sn<=inn; sn++ ) {
for( int en=1; en<=inn; en++ ) {
if( sn!=en&&edge[sn][en] ) outdeg[sn]++ ;
}
}
}
void process()
{
for( int k=1; k<=inn; k++ ) {//求传递闭包
for( int i=1; i<=inn; i++ ) {
for( int j=1; j<=inn; j++ ) {
if( edge[i][k] && edge[k][j] ) {
edge[i][j] = 1 ;
}
}
}
}
int cnt = 0 ;
for( int i=1; i<=inn; i++ ) {
cnt = 0 ;//计算i的入度
for( int j=1; j<=inn; j++ ) {
if( i == j ) continue ;
if( edge[i][j] ) cnt++ ;
if( 0==edge[i][j]&&0==edge[j][i] ) {//存在孤立点
cnt = -1 ; break ;
}
}
if( -1 == cnt ) pwd2text[i] = -1 ;
else pwd2text[i] = inn - cnt ;
}
flen = strlen( fword ) ; int i = 0 ;
for( i=0; i<flen; i++ )
{
if( fword[i]>='a'&&fword[i]<'a'+inn ) {
int curnode = fword[i] - 'a' + 1 ;
if( -1 != pwd2text[curnode] )
fword[i] = pwd2text[curnode] + 'a' - 1 ;
else break ;
}
}
if( i == flen ) printf( "%s\n", fword ) ;
else printf( "Message cannot be decrypted.\n" ) ;
}
int main()
{
//while( scanf( "%d", &testnum ) != EOF )
scanf( "%d", &testnum ) ;
{
for( int ct=1; ct<=testnum; ct++ )
{
input() ;
process() ;
//output() ;
}//for(ct)
}//while
return 0 ;
}