Poj Solution 3140

http://poj.org/problem?id=3140

#include <stdio.h>
#include <math.h>
#include <vector>


using namespace std;
double ans, total;
vector<int> e[100100];
int s[100100];

double dfs( int k, int f ) {
    double sum = 0, t;
    for( int i=0; i<e[k].size(); i++ ) {
        if( e[k][i] != f ) {
            t = dfs( e[k][i], k );
            sum += t;
            t = (t*2)-total;
            if( t < 0 ) t = -t;
            if( t < ans ) ans = t;
        }
    }
    sum += s[k];
    return sum;
}

int main( ) {
    int n, m, i, a, b, counter=1;
    while( scanf( "%d%d", &n, &m ) == 2 && n ) {
        total = 0;
        for( i=1; i<=n; i++ ) {
            e[i].clear( );
            scanf( "%d", &s[i] );
            total += s[i];
        }

        for( i=0; i<m; i++ ) {
            scanf( "%d%d", &a, &b );
            e[a].push_back( b );
            e[b].push_back( a );
        }

        ans = total;
        dfs( 1, -1 );

        printf( "Case %d: %.0lfn", counter++, ans );
    }
    return 0;
}




											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *