poj 3140 Contestants Division

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:题中的的是无向图,使图断裂为两个部分,并且使图的两个部分的点数相差最小。

虽然是图,但是可以设置一个vis去标记哪些点被访问,在dfs过程中,已经变为了一个无根树,可以当做树去处理,没差别。如果是想缩点 + 树dp 的话,操作太多,会TLE

至于树dp是很简单的,记录点u的子树下有多少个点,点u的父亲分支有多少个点,两个相减的绝对值就是删除这条边的答案,只要枚举一次所有边即可,两个dfs可以完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define M 1000010
#define LL long long
#define INF 100000000000000LL
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

LL val[N],dp[N],up[N],ans;
int n,tot,head[N];
struct edge{
int u,v,next;
bool used;
edge(){}
edge(int __u,int __v){
u = __u; v = __v; used = false;
}
}e[2*M];
bool vis[N];

inline void add(int u,int v){
e[tot] = edge(u,v); e[tot].next = head[u]; head[u] = tot++;
}

inline LL Abs(LL x){
return x < 0 ? -x : x;
}

void dfs1(int u){
vis[u] = true; dp[u] = val[u];
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(vis[v]) continue;
dfs1(v);
dp[u] += dp[v];
}
}

void dfs2(int u){
vis[u] = true; up[u] = dp[1] - dp[u];
ans = min(ans,Abs(dp[u]-up[u]));
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(vis[v]) continue;
dfs2(v);
}
}

int main(){
int m,cas = 0;
while(scanf("%d%d",&n,&m)!=EOF){
if(!n && !m) break;
tot = 0; cl(head,-1);
for(int i = 1; i <= n; i++)
scanf("%lld",&val[i]);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
ans = INF;
cl(vis,false);
dfs1(1);
cl(vis,false);
dfs2(1);
printf("Case %d: %lld\n",++cas,ans);
}
return 0;
}