POJ 3140-Contestants Division（树形dp）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

n给节点的树，分成两个联通分支，使它们大小的绝对值最小，求这个最小值。

分析：

分成两个联通分支，即删除一条边，开始看到m（边数）和n（点数）没什么关系，但题目说的是一棵树，则m==n-1,求出所有的可能的差，取最小值即可

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define N 100010
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int used[N],head[N],len,n,m;
ll dp[N],num[N],sum;
vector<int>e[N];
/*struct edge{
int t,next;
}e[N*2];
void add(int a,int b){
e[len].t=b;
e[len].next=head[a];
head[a]=len++;
}*/
ll dfs(int root){
used[root]=;
for(int i=;i<e[root].size();i++){
int son=e[root][i];
if(used[son])continue;
num[root]+=dfs(son);
if(sum>=*num[son])
dp[root]=min(dp[root],sum-*num[son]);
else
dp[root]=min(dp[root],*num[son]-sum);
}
return num[root];
}
int main()
{
int tt=;
while(~scanf("%d%d",&n,&m)){
if(n==&&m==)break;
sum=;
for(int i=;i<=n;++i){
dp[i]=INFll;
used[i]=;
e[i].clear();
scanf("%I64d",&num[i]);
sum+=num[i];
}
int a,b;
for(int i=;i<m;++i){
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
ll minv;
if(n==)
minv=num[];
else{
dfs();
minv=dp[];
for(int i=;i<=n;++i)
if(minv>dp[i])
minv=dp[i];
}
printf("Case %d: %I64d\n",++tt,minv);
}
return ;
}