《算法竞赛进阶指南》0x54 树形DP

0x54 树形DP

285. 没有上司的舞会

题意:

上司关系构成一棵树,一个人不能和直系上司同时出现在舞会,每个人有点权,询问能同时出现在舞会上的最大权值和。(最大权独立集)

解析:

f

u

,

0

/

1

f_{u,0/1}

fu,0/1 为以

u

u

u 为根的树满足条件的最大权值和。

如果选了上司,所有儿子都不能选;如果没选上司,儿子可选可不选

{

f

u

,

0

=

max

(

f

v

,

0

,

f

v

,

1

)

f

u

,

1

=

f

v

,

0

begin{cases} f_{u, 0} = summax(f_{v, 0}, f_{v, 1}) \ f_{u, 1}= sum f_{v, 0} end{cases}

{fu,0=max(fv,0,fv,1)fu,1=fv,0

代码:


#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int read() {
	int x = 0, f = 1;
	char c = getchar();
	while(c<'0' || c>'9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c>='0' && c<='9') {
		x = x*10 + c-'0';
		c = getchar();
	}		
	return x * f;
}
void write(int x) {
	if(x < 0) 
		putchar('-'), x = -x;
	if(x > 9) 
		write(x/10);
	putchar(x%10 + '0');
}

int n, a[maxn];
int f[maxn][2];
struct edge{
	int to, nxt;
}e[maxm << 1];
int head[maxn], fa[maxn], tot, rt;
void add(int a, int b){
	e[++tot].nxt = head[a];
	e[tot].to = b;
	head[a] = tot;
}
void dfs(int u, int fa){
	f[u][1] = a[u];
	for(int i = head[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(v == fa)
			continue;
		dfs(v, u);
		f[u][0] += max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		add(v, u);
		fa[u] = v;
	}
	for(int i = 1; i <= n; i++)
		if(fa[i] == 0)
			rt = i;
	dfs(rt, 0);
	cout << max(f[rt][0], f[rt][1]) << endl;
	return 0;
}

选课

题意:

n

n

n 门课,每门课有一定的学分,需要选

m

m

m 门。有些课有先修课,选了先修课才能选当前课。询问最多学分。

解析:

f

u

,

k

f_{u, k}

fu,k 为以

u

u

u 为根的子树中,选

k

k

k 门课的最大学分。

对每个节点

u

u

u 来说,分组背包,从每个儿子中选一定的课。

代码:


#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e2+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int read() {
	int x = 0, f = 1;
	char c = getchar();
	while(c<'0' || c>'9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c>='0' && c<='9') {
		x = x*10 + c-'0';
		c = getchar();
	}		
	return x * f;
}
void write(int x) {
	if(x < 0) 
		putchar('-'), x = -x;
	if(x > 9) 
		write(x/10);
	putchar(x%10 + '0');
}
struct edge{
	int to, nxt;
}e[maxm << 1];
int head[maxn], fa[maxn], tot, rt;
void add(int a, int b){
	e[++tot].nxt = head[a];
	e[tot].to = b;
	head[a] = tot;
}
int n, m, a[maxn];
int f[maxn][maxm];

void dfs(int u){
	for(int i = head[u]; i; i = e[i].nxt){
		int v = e[i].to;
		dfs(v);
	}
	
	for(int i = head[u]; i; i = e[i].nxt){
		int v = e[i].to;
		for(int j = m; j > 0; j--){
			for(int k = 0; k < j; k++)
				f[u][j] = max(f[u][j], f[u][j-k]+f[v][k]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	m++;
	//memset(f, -INF, sizeof(f));
	for(int i = 1; i <= n; i++){
		cin >> fa[i] >> f[i][1];
		add(fa[i], i);
	}	
	dfs(0);
	cout << f[0][m];
	return 0;
}

积蓄程度

题意:

一棵树,根节点可以流出无限水,叶子节点可以吸收无限水,每条边有流量限制。询问以哪个点为根节点时,叶子节点吸收的水最多。

解析:

第一次扫描:

f

u

f_u

fu 为以1为根节点时,以

u

u

u 为根的子树中,吸收的水量。

v

v

v

u

u

u 的儿子:

{

f

u

+

=

m

i

n

(

f

v

,

w

(

u

,

v

)

)

,

d

e

g

v

=

1

f

u

+

=

w

(

u

,

v

)

,

d

e

g

v

1

begin{cases} f_u += min(f_v, w(u, v)), & deg_v = 1\ f_u += w(u, v), & deg_v neq 1 end{cases}

{fu+=min(fv,w(u,v)),fu+=w(u,v),degv=1degv=1

第二次扫描:

g

u

g_u

gu 为以

u

u

u 为根节点时,最大流量。

设第一次扫描时

v

v

v

u

u

u 的儿子。假设根节点由

u

u

u 变为

v

v

v

g

v

g_v

gv 包括两部分:

  • 一部分是第一次扫描的

    f

    v

    f_v

    fv

  • 一部分是流向

    u

    u

    u 进而流向其他节点

u

u

u 而言,从

u

u

u

v

v

v 的流量为

m

i

n

(

f

j

,

w

(

i

,

j

)

)

min(f_j, w(i,j))

min(fj,w(i,j)),流向

v

v

v 之外的流量为

g

u

m

i

n

(

f

j

,

w

(

i

,

j

)

)

g_u - min(f_j, w(i,j))

gumin(fj,w(i,j))。所以

g

v

g_v

gv 的第二部分为

m

i

n

(

w

(

u

,

v

)

,

g

u

m

i

n

(

f

j

,

w

(

i

,

j

)

)

)

min(w(u,v), g_u - min(f_j, w(i,j)))

min(w(u,v),gumin(fj,w(i,j)))。也需要按照度是否为1讨论一下:

{

g

v

=

f

v

+

w

(

u

,

v

)

d

e

g

u

=

1

g

v

=

f

v

+

m

i

n

(

g

u

w

(

u

,

v

)

,

w

(

u

,

v

)

)

d

e

g

u

1

,

d

e

g

v

=

1

g

v

=

f

v

+

m

i

n

(

g

u

m

i

n

(

f

v

,

w

(

u

,

v

)

)

,

w

(

u

,

v

)

)

,

d

e

g

u

1

,

d

e

g

v

1

begin{cases} g_v = f_v+ w(u, v) & deg_u = 1\ g_v = f_v + min(g_u-w(u,v), w(u, v)) &deg_u neq 1 ,deg_v = 1\ g_v = f_v + min(g_u-min(f_v, w(u,v)), w(u,v)),& deg_u neq 1 ,deg_v neq 1 end{cases}

gv=fv+w(u,v)gv=fv+min(guw(u,v),w(u,v))gv=fv+min(gumin(fv,w(u,v)),w(u,v)),degu=1degu=1,degv=1degu=1,degv=1

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;


#define int ll
struct edge{
	int to, nxt, w;
}e[maxn << 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){
	e[++tot].nxt = head[a];
	e[tot].to = b;
	e[tot].w = c;
	head[a] = tot;
}
int n, m;
ll f[maxn], g[maxn], deg[maxn];
void dfs(int u, int fa){
	f[u] = 0;
	for(int i = head[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(v == fa)
			continue;
		dfs(v, u);
		if(deg[v] == 1)
			f[u] += e[i].w;
		else
			f[u] += min(e[i].w, f[v]);
	}
}
void dfs2(int u, int fa){
	for(int i = head[u]; i; i = e[i].nxt){
		int v = e[i].to;
		if(v == fa)
			continue;
		if(deg[u] == 1)
			g[v] = f[v] + e[i].w;
		else if(deg[v] == 1)
			g[v] = f[v] + min(g[u]-e[i].w, e[i].w);
		else
			g[v] = f[v] + min(g[u]-min(f[v], e[i].w), e[i].w);
		dfs2(v, u);
	}
}
void solve(){
	cin >> n;
	memset(deg, 0, sizeof(deg));
	tot = 0;
	memset(head, 0, sizeof(head));
	for(int i = 1; i < n; i++){
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
		deg[a]++; deg[b]++;
	}
	dfs(1, 0);
	g[1] = f[1];
	dfs2(1, 0);
	ll res = 0;
	for(int i = 1; i <= n; i++)
		res = max(res, g[i]);
	cout << res << endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int T;
	cin >> T;
	while(T--)
		solve();
	return 0;
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇

)">
下一篇>>