Cod sursa(job #165869)

Utilizator amadaeusLucian Boca amadaeus Data 27 martie 2008 01:06:41
Problema ADN Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.58 kb
// ADN - infoarena (KMP + ciclu hamiltonian de cost minim)

#include <stdio.h>
#include <string.h>

#define NX 19
#define LX 30010
#define INF 666666

int N, M, res;

int pi[ NX ][ LX ], a[ NX ][ NX ], b[ NX ][ NX ];
int L[ NX ], del[ NX ], map[ NX ], sol[ NX ], st[ NX ], V[ NX ];
char cuv[ NX ][ LX ];

void calc_pi( int x ) {
	int i, k;
	for( pi[x][0] = k = -1, i = 1; i <= L[x]; pi[x][i++] = ++k )
		while( cuv[x][i] != cuv[x][k+1] && k>=0 )
			k = pi[x][k];
}

void cit() {
	int i;
	
	scanf( "%d ", &N );

	for( i = 1; i <= N; i++ ) {
		cuv[i][0] = ' ';
		gets( cuv[ i ] + 1 );
		L[i] = strlen( cuv[i] + 1 );
		calc_pi( i );
	}
}

int match( int x, int y ) {
	int i, k;

	for( i = 1, k = 0; i <= L[x]; i++ ) {
		while( cuv[x][i] != cuv[y][k+1] && k >= 0 )
			k = pi[y][k];
		if( ++k == L[y] )
			break;
	}
	return L[y] - k;
}

void normalize() {
	int i, j, Min, pMin;

	for( i = 1; i <= N; i++ ) {
		Min = INF, pMin = 0;
		for( j = 1; j <= N; j++ )
			if( i != j ) {
				a[i][j] = match( i, j );
				if( Min > a[i][j] )
					Min = a[i][j], pMin = j;
			}
		if( Min <= 0 )
			del[ pMin ] = 1;
	}
	
	for( i = 1, M = 0; i <= N; i++ )
		if( del[i] == 0 )
			map[ ++M ] = i;

	for( i = 1; i <= M; i++ )
		for( j = 1; j <= M; j++ )
			b[i][j] = a[ map[i] ][ map[j] ];
}

int check() {
	int i, s;
	
	for( s = 0, i = 1; i < M; i++ )
		s += b[ st[i] ][ st[i+1] ];

	if( res > s ) {
		res = s;
		memcpy( sol, st, sizeof( st ) );
	}

	return 0;
}

int baga( int k ) {
	int i;
	
	if( k > M ) {
		check();
		return 0;
	}

	for( i = 1; i <= M; i++ )
		if( V[i] == 0 && (b[ st[k-1] ][ i ] != 0 || k == 1) ) {
			V[i] = 1; st[k] = i;
			baga( k+1 );
			V[i] = 0;
		}
	return 0;
}

void rez() {

	normalize();
	
	res = INF;
	baga( 1 );
}

void scr() {
	int i, j;
/*
	for( i = 1; i <= N; i++ ) {
		for( j = 1; j <= L[i]; j++ )
			printf( "%d ", pi[i][j] );
		printf( "\n" );
	}

	printf( "\n" );

	for( i = 1; i <= N; i++ ) {
		for( j = 1; j <= N; j++ )
			printf( "%d ", a[i][j] );
		printf( "\n" );
	}

	printf( "\n" );
	for( i = 1; i <= M; i++ )
		printf( "%d ", map[i] );

	printf("\n" );
	printf( "%d\n", L[ map[1] ] + res );

	for( i = 1; i <= M; i++ )
		printf( "%d ", map[ sol[i] ] );
*/
	fputs( cuv[ map[ sol[1] ] ] + 1, stdout );
	for( i = 2; i <= M; i++ )
		fputs( cuv[ map[ sol[i] ] ] + L[ map[sol[i]] ] - b[ sol[i-1] ][ sol[i] ] + 1, stdout );
	printf( "\n" );
}

int main() {
	freopen( "adn.in", "r", stdin );
	freopen( "adn.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}