P4410 [HNOI2009] 无归岛 题解

· · 题解

DFS树上DP

如果没有环，这个题就是树上最大权独立集。

由于原图是仙人掌，需要特殊处理，这里使用DFS树。仙人掌生成的DFS树有一个特点：每个点只有一条返祖边，并且任两个环不共用一条边。

（以下称一个环中DFS树上深度最小的节点为环顶）

根据DFS树的形态简单推理就可以得到这个问题是可以用类似基环树上DP的方式，状态为 f[x][0/1][0/1] 的 DP 解决的。（第一维为当前节点，第二维表示当前节点是否选择，第三维表示当前节点所在的 非当前节点为环顶的环 的环顶 是否选择）

细节最多的就在第三维的设计与转移上：

由于之前提到的仙人掌生成的DFS树的性质，我们只需要把注意力放在返祖边以及其的起点和终点上。终点只需把 f[x][1][1] 赋为 \inf 即可，问题主要为找到环顶以及环顶的更新（一个点为环顶是相对这个环的，在其它地方它可能还是照常更新），于是我们还要一个 top[] 记录该节点所在 当前节点所在的 非当前节点为环顶的环 的环顶，以便回溯时更新。

在状态更新时如果父节点不为相对于这个环（由于仙人掌的性质，一条边其实可以代表一个环）的环顶，正常更新；如果为环顶，注意子节点的第二维对应的是父节点的第一维。

代码：(防越界就偷懒开了long long)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5,INF=0x3f3f3f3f;
vector<int> lin[MAXN];
int n,u,v,m,fa[MAXN],bjt[MAXN],top[MAXN],num[MAXN],dep[MAXN];
ll dp[MAXN][2][2];
void DFS(int x){
    bjt[x]=1,dp[x][1][0]=dp[x][1][1]=num[x];
    for(int to:lin[x]) if(to!=fa[x]){
        if(bjt[to]){ if(dep[to]<dep[x]) top[x]=to,dp[x][1][1]=-INF; }
        else{
            fa[to]=x,dep[to]=dep[x]+1,DFS(to);
            if(top[to]!=x){
                top[x]=top[to];
                dp[x][0][0]+=max(dp[to][1][0],dp[to][0][0]);
                dp[x][1][0]+=dp[to][0][0];
                dp[x][0][1]+=max(dp[to][1][1],dp[to][0][1]);
                dp[x][1][1]+=dp[to][0][1];
            }
            else{
                dp[x][0][0]+=max(dp[to][0][0],dp[to][1][0]);
                dp[x][1][0]+=dp[to][0][1];
                dp[x][0][1]+=max(dp[to][0][0],dp[to][1][0]);
                dp[x][1][1]+=dp[to][0][1];
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&u,&v),lin[u].push_back(v),lin[v].push_back(u);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    DFS(1);
    printf("%lld",max(max(dp[1][0][0],dp[1][0][1]),max(dp[1][1][0],dp[1][1][1])));
    return 0;
}
/*
4 4
1 2
2 3
3 4
4 1
20 10 30 15

3 3
1 2
2 3
3 1
20 10 30

2 2
1 2
2 1
20 10
*/