3140.txt

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

Source

Problem Id:3140  User Id:fzk 
Memory:3880K  Time:750MS
Language:G++  Result:Accepted

Source 

#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: %.0lf\n", counter++, ans );
	}
	return 0;
}