树形DP

- 选课
- 积蓄程度

树形DP

1. 选课
2. 积蓄程度

1. 选课

题目链接

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 $a$ 是课程 $b$ 的先修课即只有学完了课程 $a$ ,才能学习课程 $b$ 。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

输入格式
第一行有两个整数 $N, N$ 用空格隔开。 $(1\leq N \leq 300 , 1 \leq M \leq 300)$
接下来的 $N$ 行，第 $I + 1$ 行包含两个整数 $k_{i}$ 和 $s_{i}$ ， $k_{i}$ 表示第 $I$ 门课的直接先修课， $s_{i}$ 表示第 $I$ 门课的学分。若 $k_{i}=0$ 表示没有直接先修课 $(1\leq k_{i}\leq N$ , $1\leq s_{i}\leq20)$ 。

输出格式
只有一行，选 $M$ 门课程的最大得分。

输入输出样例

输入
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出
13

题目分析

典型的树形DP，森林结构，为简便起见，我们将虚拟课程0号节点作为根节点，这样就构成了一个 $n + 1$ 个节点的树。

设 $f [x] [t]$ 表示在以 $x$ 为根的子树中选 $t$ 门课能够获得的最高学分。对于 $x$ 的每个儿子结点 $y$ ，我们可以在该子树中选修若干门课，只要 $x$ 的所有子树选修的课总数为 $t - 1$ ，在这个过程中获得尽量多的学分。转移方程如下：

$t>0:f[x][y]=max\{\sum_{i=1}^{p}{f[y_{i}][c_{i}]}\}+a[x]$ ， $p$ 是 $x$ 的子结点个数， $\sum_{i=0}^{p}c_{i}=t-1$
$t = 0 : f [x] [0] = 0$

有 $p$ 组物品。每组物品都有 $t - 1$ 个，其中第 $i$ 组的第 $j$ 个物品体积为 $j$ ，价值为 $f [y i] [j]$ 。要从 $p$ 个物品中每组至多选择一种物品，背包的总体积为 $t - 1$ 。每组物品都有 $t - 1$ 个，如果该子树的结点个数 $< t - 1$ ，怎么办？其实不影响，可以想象成在叶节点下还有很多“隐形”的结点课程，所有的学分都是 $0$ ，如果子树的结点个数 $< t - 1$ ，不够的课程可以从这些“隐形”的课程中选取，不影响正确结果。

目标： $f [0] [m + 1]$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n,m,h[1000],cnt,f[2000][2000],s[1000],output[1000];
struct node
{
	int next , to , val ;
}edg[1000];

inline int maxx ( int x , int y )
{
	return x > y ? x : y ; 
}

inline int minn ( int x , int y )
{
	return x < y ? x : y ;
}

inline void add( int u , int v , int val )
{
	++cnt;
	edg[cnt].next = h[u] ;
	edg[cnt].to = v ;
	edg[cnt].val = val ;
	h[u] = cnt ;
}

void dfs ( int u , int fa )
{
	f[u][1] = s[u] ;
	for ( int i = h[u] ; i ; i = edg[i].next )
	{
		int v = edg[i].to ;
		if ( v == fa ) continue ;
		dfs ( v , u ) ;
		for ( int j = n + 1 ; j >= 1 ; --j )
			for ( int k = 0 ; k < j ; ++k )// 逆序能够保证此时f[u][j-k]不包括v这颗子树
				f[u][j] = maxx ( f[u][j] , f[v][k] + f[u][j-k] );
	}
}

inline int readint()
{
	int x = 0 , f = 1 ; char c = getchar() ;
	while ( c > '9' || c < '0' ) { if ( c == '-' ) f = -1 ; c = getchar() ; }
	while ( c >= '0' && c <= '9') { x = x * 10 + c - '0' ; c = getchar() ; }
	return f * x ; 
}

int main()
{
	n = readint() ; m = readint() ;
	for ( int i = 1 ; i <= n ; ++i )
	{
		int k = readint() ; s[i] = readint() ;
		add ( i , k , 1 ) ; add ( k , i , 1 ) ;
	}
	dfs( 0 , -1 ) ;
	printf ( "%d\n" , f[0][m+1] ) ; 
	return 0 ;
}

反思与总结

1.森林需要额外加一0点
2.背包问题要注意使用逆序
~~3.注意应开数组大小~~

2. 积蓄程度

题目链接

积蓄程度

题目描述

有一个树形的水系，由 $N - 1$ 条河道和 $N$ 个交叉点组成。
我们可以把交叉点看作树中的节点，编号为 $1 N$ ，河道则看作树中的无向边。
每条河道都有一个容量，连接 $x$ 与 $y$ 的河道的容量记为 $c (x, y)$ 。
河道中单位时间流过的水量不能超过河道的容量。
有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。
除了源点之外，树中所有度数为 $1$ 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。
也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。
在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。
除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。
整个水系的流量就定义为源点单位时间发出的水量。
在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

输入格式
输入第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。
每组测试数据，第一行包含整数 $N$ 。 $(1\leq N\leq 2 \times 10^5 )$
接下来 $N - 1$ 行，每行包含三个整数 $x, y, z$ ，表示 $x ， y$ 之间存在河道，且河道容量为 $z$ 。
节点编号从 $1$ 开始。

输出格式
每组数据输出一个结果，每个结果占一行。
数据保证结果不超过 $2^{31}-1$ 。

输入输出样例

输入
1
5
1 2 11
1 4 13
3 4 5
4 5 10
输出
26

题目分析

本题题解可参考 $0 X 54$ 树形dp二次扫描与换根法。每个点都有可能是源点，即每个点都可能当作根。这是个不定根的树形dp问题。可以通过“二次扫描与换根法”得解.
1.第一次扫描时，任选一个点为根，进行树形dp，求出 $d [x]$ ，表示以 $x$ 为根的子树中，把 $x$ 作为源点，从 $x$ 出发流向子树的最大水量。

$d[x]=\sum\begin{cases} min(d[y],c(x,y))\qquad y的度数>1\\ c(x,y)\qquad \qquad \qquad y的度数=1 \end{cases}$

2.第二次扫描时，从刚才选出的根出发，对整棵树执行dfs，然后自顶向下递推，对每个点执行“换根”操作，计算结果。设 $f [x]$ 表示把 $x$ 作为源点，流向整个水系，最大流量是多少。对于根结点 $r o o t$ ，显然有 $f [r o o t] = d [r o o t]$ 。假设 $f [x]$ 已经被求出，考虑其子结点 $y$ 。
$f [y]$ 包含两部分：
1.从 $y$ 流向以 $y$ 为根的子树的流量，即 $d [y]$ 。
2.从 $y$ 沿着到父结点 $x$ 的河道，进而流向水系中其他部分的流量。
把 $x$ 作为源点总流量为 $f [x]$ ，从 $x$ 流向 $y$ 的流量为 $m i n (d [y], c (x, y))$ ，所以从 $x$ 流向除 $y$ 以外其他部分的流量就是二者之差。于是，把 $y$ 作为源点，先流向 $x$ ，再流向其他部分的流量就是这个差与 $c (x, y)$ 取最小值的结果

$f[y]=d[y]+\begin{cases} min(f[x]-min(d[y],c(x,y)),c(x,y))\qquad x的度数>1\\ c(x,y)\qquad \qquad \qquad \qquad \qquad \qquad \qquad x的度数=1 \end{cases}$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int t,n,h[200050],cnt,f[200050],d[200050],dgr[200050] ;
int ans = -0x7fffffff ;
struct node
{
	int next , to , val ;
}edg[400050] ;

inline int maxx ( int x , int y )
{
	return x > y ? x : y ; 
}

inline int minn ( int x , int y )
{
	return x < y ? x : y ;
}

inline void add( int u , int v , int val )
{
	++cnt;
	edg[cnt].next = h[u] ;
	edg[cnt].to = v ;
	edg[cnt].val = val ;
	h[u] = cnt ;
}

void dp ( int u , int fa )//第一次搜索
{
	d[u] = 0 ;
	for ( int i = h[u] ; i ; i = edg[i].next )
	{
		int v = edg[i].to ;
		if ( v == fa ) continue ;
		dp ( v , u ) ;
		if ( dgr[v] == 1) d[u] += edg[i].val ;
		else d[u] = d[u] + minn ( edg[i].val , d[v] ) ;
	}
}

void dfs ( int u , int fa )//第二次搜索
{
	for ( int i = h[u] ; i ; i = edg[i].next )
	{
		int v = edg[i].to ;
		if ( v == fa ) continue ;
		if ( dgr[u] == 1 ) f[v] = d[v] + edg[i].val ;
		else f[v] = d[v] + minn ( f[u] - minn ( d[v] , edg[i].val ) , edg[i].val ) ;
		dfs ( v , u ) ;
	}
}

inline int readint()
{
	int x = 0 , f = 1 ; char c = getchar() ;
	while ( c > '9' || c < '0' ) { if ( c == '-' ) f = -1 ; c = getchar() ; }
	while ( c >= '0' && c <= '9') { x = x * 10 + c - '0' ; c = getchar() ; }
	return f * x ; 
}

int main()
{
	t = readint() ;
	while ( t-- )
	{
		memset ( h , 0 , sizeof(h) ) ;
		memset ( dgr , 0 , sizeof(dgr) ) ;
		memset ( edg , 0 , sizeof(edg) ) ;
		memset ( f , 0 , sizeof(f) ) ;
		memset ( d , 0 , sizeof(d) ) ;//多组数据，需初始化
		ans = cnt = 0 ;
		n = readint () ;
		for ( int i = 1 ; i <= n - 1 ; ++i )
		{
			int x = readint() , y = readint() , z = readint() ;
			add ( x , y , z ) ; add ( y , x , z ) ;
			dgr[x]++ ; dgr[y]++ ; 
		}
		dp ( 1 , 0 ) ;//d[x]
		f[1] = d[1] ;
		dfs ( 1 , 0 ) ;//f[x]
		for ( int i = 1; i <= n ; ++i )
			ans = maxx ( ans , f[i] ) ;
		printf ( "%d\n" , ans ) ;
	}
	return 0 ;
}

反思与总结

多组数据要注意初始化
掌握二次扫描与换根法
$d g r$ 的使用
~~不知道哪些变量需要初始化就全部初始化~~