没有上司的舞会

题目描述

某大学有 $n$ 个职员，编号为 $1\ldots n$。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。

第 $(n + 2)$ 到第 $2n$ 行，每行输入一对整数 $l, k$，代表 $k$ 是 $l$ 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$，$-128 \leq r_i\leq 127$，$1 \leq l, k \leq n$，且给出的关系一定是一棵树。

思路：

1
2
3

//没有上司的舞会
//定义f[u][0]为u节点没有被选，u所在子树的最大权值和
//f[u][1]表示u被选时候的子树最大权值和

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
const int N=6005;
vector<int>G[N];
int n;
int a[N];
int f[N][2];
void dfs(int u,int fa)
{
	f[u][0]=0;
	f[u][1]=a[u];
	for(auto v:G[u])
	{
		if(v!=fa)
		{
			dfs(v,u);
			f[u][0]+=max(f[v][0],f[v][1]);
			f[u][1]+=f[v][0];
		}
	}
	
}
int main()
{
	cin>>n;
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,n-1)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	cout<<max(f[1][0],f[1][1]);
}

[CTSC1997] 选课

题目描述

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

输入格式

第一行有两个整数 $N$ , $M$ 用空格隔开。( $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} \leq 20$）。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

对一棵子树,要想选其中的点,根节点是必须选的

所以不妨设根节点为1号节点

不妨设f[now][j][k]表示以now为根节点的子树

考虑前j个节点选k门课的方案数

因为1号节点是根节点,显然递推起点f[now][1][1]=val[now]

这样很容易得到状态转移方程

f[now][j][k]=max(f[now][j-1][k],f[son][所有节点数][l]+f[now][j-1][k-l]);

注意可以滚动

这就是树上背包

#include<bits/stdc++.h>
#define maxn 1000
using namespace std;
int n,m,f[maxn][maxn],head[maxn],cnt;
struct edge
{
    int to,next; 
}e[maxn];
void add(int from,int to)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
void dp(int now)
{
    for(int i=head[now];i;i=e[i].next)
    {
        int go=e[i].to;
        dp(go);
        for(int j=m+1;j>=1;j--)
        {
            for(int k=0;k<j;k++)
            {
                f[now][j]=max(f[now][j],f[go][k]+f[now][j-k]);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int fa;
        cin>>fa;
        cin>>f[i][1];
        add(fa,i);
    }
    dp(0);
    cout<<f[0][m+1];
    return 0;
}

Accumulation Degree

我们可以对于每个点进行一次树形dp来求，但是显然时间复杂度很高，会TLE...

我们考虑先对1号点dp一次，并且维护每个结点的dp值，表示当前结点流向其子树的最大流量，然后再dfs一次进行换根。

注意换根那里得的表达，需要推理一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,rt,d[maxn],f[maxn],deg[maxn];
struct node
{
    int to,w;
    node(int x=0,int y=0):to(x),w(y){}
};
vector<node> G[maxn];
#define cls(a,b) memset(a,b,sizeof(a))
void init(){
    cls(d,0);cls(f,0);cls(deg,0);
    for(int i=1;i<=2e5;i++)G[i].clear();
}
inline void add_edge(int from,int to,int w)
{
    G[from].push_back(node(to,w)),++deg[from];
    G[to].push_back(node(from,w)),++deg[to];
}
void read_and_parse()
{
      cin>>n;
    for(int i=1;i<n;i++){
        int from,to,w;
        cin>>from>>to>>w;
        add_edge(from,to,w);
    }
}

void dfs1(int u,int fa){
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].to,w=G[u][i].w;
        if(v==fa)continue;
        dfs1(v,u);
        if(deg[v]==1)d[u]+=w;
        else d[u]+=min(w,d[v]);
        //流量限制
    }
}
//考虑换根
void dfs2(int u,int fa){
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].to,w=G[u][i].w;
        if(v==fa)continue;
        if(deg[u]==1)f[v]=d[v]+w;
        else f[v]=d[v]+min(f[u]-min(w,d[v]),w);
        dfs2(v,u);
    }
}

void solve()
{
    rt=1;
    dfs1(rt,0);
    f[rt]=d[rt];
    dfs2(rt,0);
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
   cout<<ans<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        init();
        read_and_parse();
        solve();
    }
    return 0;
}