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

using namespace std;

vector<long> con[100001];
_int64 val[100001];
_int64 sum,min;
long n;
int u[100001];

_int64 search(long x)
{
	_int64 s;
	_int64 z,mm;
	u[x]=1;
	s=val[x];
	mm=min;
	for (vector<long> ::iterator i = con[x].begin(); i != con[x].end(); i++)
		if (!u[*i])
		{
			z=search(*i);
			if (mm>abs(sum-z-z)) mm=abs(sum-z-z);
			s=s+z;
		}
	if (mm>abs(s+s-sum)) mm=abs(s+s-sum);
	if (mm<min) min=mm;
	return s;
}

int main()
{
	long i,p,m;
	long b,c;
	p=1;
	scanf("%ld%ld",&n,&m);
	while (!(n==0&&m==0))
	{
		for (i=1;i<=n;i++)
			con[i].clear();
		sum=0;
		for (i=1;i<=n;i++)
		{
			scanf("%I64d",&val[i]);
			sum=sum+val[i];
		}
		for (i=1;i<=m;i++)
		{
			scanf("%ld%ld",&b,&c);
			con[b].push_back(c);
			con[c].push_back(b);
		}
		min=abs(sum-val[1]-val[1]);
		memset(u,0,sizeof(u));
		search(1);
		printf("Case %ld: %I64d\n",p,min);
		p++;
		scanf("%ld%ld",&n,&m);
	}
	return 0;
}

• LL表示该数为long long类型，值该是多少就是多少 (1138) wywcgs 2006-12-09 22:42:06