# Poj Solution 2669

```http://poj.org/problem?id=2669

#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 %dn", 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;
}

```
This entry was posted in poj. Bookmark the permalink.