题解：P10933 创世纪

题意

可以抽象成一个图论问题。

给你

n

个点的有向图，每个点恰好有一个出边（可能有自环），选出尽可能多的点，使得每个被选出的点

x

，都至少有一个指向

x

的点没被选。

思路

可以想到 DP。

这是一棵树吗？显然不是，因为边数等于点数，那就是一棵基环树了！！！

基环树 DP 的一般思路就是先断掉一条边，使其变成一个普通的树形 DP 进行求解，最后考虑上删边的影响。

那我们就先考虑这个树上的 DP。

树上 DP

和没有上司的舞会很像。

状态

设

dp_{u,0/1}

表示以

u

为根的子树，并且选或不选

u

最多能选择的点数。

算是一个经典模型了，一般都会这么设。

转移方程

如果

u = 0

，那么他的儿子都可以选，当然也可以不选。所以求最大值。转移方程就是

dp_{u,0}=\sum{\max(dp_{v,0},dp_{v,1})}

。

如果

u = 1

，那么他至少要有一个儿子不选，不选的儿子肯定是值最小的，这样

dp_{u,1}

才会大。即

dp_{u,1} = 1 + dp_{u}{0} - \min(dp_{v,1} - dp_{v,0})

。

边界条件

因为要求和，所以全赋值为

0

，即

dp_{u,0/1} = 0

。

删边

用两次 DP 来解决。

考虑

u

选不选，一次设

u

要选，一次设

u

不选。

最后答案取最大值就行了。

代码

细节都在注释里。

CPP

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;

int n,a[N];

vector<int> e[N];

int dfn[N],dp[N][2];

int vis[N];
void dfs(int u,int root,bool flag){
	dfn[u] = true;
	int mi = INF;
	for (auto v :e[u]){
		if (v == root) continue;//防止死循环
		dfs(v,root,flag);
		dp[u][0] += max(dp[v][1],dp[v][0]);
		mi = min(dp[v][1] - dp[v][0],mi);//维护最小值
	}
	dp[u][1] = 1 + dp[u][0];
	if (u != a[root] or !flag){	
		if (mi >= 0) dp[u][1] -= mi;
	}
}
int main()
{
	int n;cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		e[a[i]].push_back(i);//还要在树的内部 DP，所以建反图
	}
	int sum = 0;
	for (int x = 1;x <= n;x++){//基环森林
		if (!dfn[x]){
			while(!vis[x]){
				vis[x] = true;
				x = a[x];
			}//求环
			dfs(x,x,1);
			int ans = dp[x][0];
			dfs(x,x,0);
			sum += max(dp[x][1],ans);
		}

	}
	cout << sum;
	return 0;	
}

题解：P10933 创世纪

文章操作

题意

思路

树上 DP

状态

转移方程

边界条件

删边

代码

相关推荐

评论

题解：P10933 创世纪