2669.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2669  User Id:fzk 
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
double dis[100][100];
int n, m;
bool e[100][100];
int son[100];
double len[100];
bool sign [100];
int v2[100], v[100], vn2, vn;
int calc2( int a, int f )
{
	int i, s, j;
	
	for( s=1,i=0, j=0; i<m; i++ )
	if( i!=f && e[a][i] )
	{
		s = ( s*calc2( i, a ) ) % 2005;
		j++;
	}

	while( j )
	{
		s = (s*j)%2005;
		j--;
	}

	return s;
}
void calc( )
{
	int i, j, k;
	double t, ans, s;	
	memset( e, 0, sizeof(e) );		
	m = n;
	ans = 0;
	vn = n;
	for( i=0; i<vn; i++ )
	{
		v[i] = i;
		son[i] = i;
		len[i] = 0;
	}
	while( vn > 1 )
	{
		if( vn == 2 )
		{
			e[ v[0] ][ v[1] ] = e[ v[1] ][ v[0] ] = 1;
			ans += dis[ v[0] ][ v[1] ];
			break;
		}
		vn2 = 0;
		for( i=0; i<vn; i++ )
		{
			s = 10000000;
			for( j=0; j<vn; j++ )
			if( j != i )
			for( k=j+1; k<vn; k++ )
			if( k != i )
			{
				if( s > ( t = (dis[v[j]][v[i]]+dis[v[i]][v[k]]-dis[v[j]][v[k]])/2 ) )
					s = t;
			}
			if( s == 0 )
			{
				v2[ vn2++ ] = v[i];
				sign[ v[i] ] = 1;
			}
			else
			{
				v2[ vn2++ ] = m;
				sign[m] = 1;
				len[ m ] = s + len[v[i]];
				son[ m ] = son[v[i]];
				e[m][v[i]] = e[v[i]][m] = 1;				
				ans += s;				
				m++;
			}
		}
		int temp;
		temp = vn;
		vn = 0;
		for( i=0; i<vn2; i++ )
		if( sign[ v2[i] ] )
		{
			for( j=i+1; j<vn2; j++ )
			if( sign[ v2[j] ] )
			{
				dis[v2[j]][v2[i]] = dis[v2[i]][v2[j]] = dis[ son[v2[i]] ][ son[v2[j]] ] - len[ v2[i] ] - len[ v2[j] ];
				if( dis[v2[i]][v2[j]] == 0 )
				{
					for( k=0; k<m; k++ )
						if( e[ v2[j] ][ k ] )
						{
							e[ v2[j] ][ k ] = e[ k ][ v2[j] ] = 0;
							e[ v2[i] ][ k ] = e[ k ][ v2[i] ] = 1;
						}
					sign[ v2[j] ] = 0;
				}
			}
			v[ vn++ ] = v2[i];
		}
		if( vn >= temp )
			while( printf( "ft!" ) );
	}
	int temp = calc2( 0, -1 );
	printf( "%.0f %d\n", ans*2, temp  );
}
int main()
{
	int i, j;	
	while( 1 )
	{
		scanf( "%d", &n );

		if( n == 0 ) break;

		for( i=0; i<n; i++ )
		{
			for( j=0; j<n; j++ )
				scanf( "%lf", &dis[i][j] );
		}
		calc();
	}
	return 0;
}