POJ -- 3140

时间:2023-12-27 15:24:13
     #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define MAXN 1000010
#define LL long long
const LL INF = 0x7fffffffffffff;
using namespace std;
typedef struct{
int to,next;
}Node;
Node edge[*MAXN];
int vis[MAXN/],head[MAXN/],val[MAXN/];
LL sum[MAXN/],all_sum,ans;
LL My_abs(LL tmp){return tmp < ? -tmp : tmp;}
void addedge(int u,int v,int k){
edge[k].to = v;
edge[k].next = head[u];
head[u] = k;
}
LL dfs_sum(int s){
vis[s] = ;
sum[s] = val[s];
for(int i = head[s];~i;i = edge[i].next){
int u = edge[i].to;
if(!vis[u]) sum[s] += dfs_sum(u);
}
return sum[s];
}
void dfs_minabs(int s){
vis[s]= ;
for(int i = head[s];~i;i = edge[i].next){
int u = edge[i].to;
if(!vis[u]){
dfs_minabs(u);
ans = min(ans,My_abs(all_sum - *sum[u]));
}
}
}
int main(){
int n,m,cas = ;
freopen("in.c","r",stdin);
while(~scanf("%d%d",&n,&m) && (m+n) ){
int k = ,tmp,u,v;
all_sum = ;
for(int i = ;i <= n;i ++) scanf("%d",&tmp),val[i] = tmp,all_sum += tmp;
memset(head,-,sizeof(head));
for(int i = ;i < m;i ++){
scanf("%d%d",&u,&v);
addedge(u,v,k++);
addedge(v,u,k++);
}
memset(vis,,sizeof(vis));
dfs_sum();
ans = INF;
memset(vis,,sizeof(vis));
dfs_minabs();
if(n == ) ans = val[];
printf("Case %d: %lld\n",++cas,ans);
}
return ;
}