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;
}