题解 P2478 【[SDOI2010]城市规划】

ix35 · 2020-03-22 09:16:27 · 题解

一道仙人掌上 DP 的题。

首先是 Tarjan 找环，然后对环上 DP 和树上 DP 分别讨论：

设 dp(i,0) 表示选了 i 时 i 的子树最大贡献，dp(i,1) 表示选了 i 的某个儿子时 i 的子树的最大贡献，dp(i,2) 表示 i 和儿子都没选时子树的最大贡献。

树上 DP 部分：

设 v 为 u 的子结点，则先令 dp(u,0)=HX_u，然后转移：

而 dp(u,1) 略微麻烦。因为只能选恰好一个儿子，别的儿子都按照 dp(u,2) 的方式转移，只有一个儿子是通过 dp(v,0) 的形式转移的，所以只需要统计相对于 dp(u,2) 的增量即可，即：

环上 DP 部分：

计算环顶 DP 的值，设环顶为 u，环上的点按深度从大到小依次为 v_1,\ldots,v_k，那么 u=v_k，考虑转移：

先定义一个 Calc(l,r)， 表示如果规定了 v_l 和 v_r 不能选，中间的点只要按照规则可以随便选，那么最大的总 DP 值为多少，这就是个链上的 DP，和树上 DP 转移相似。

对于 dp(u,0)，增量为 dp(v_{k-1},2)+dp(v_1,2)+Calc(3,k-3)。

对于 dp(u,2)，增量为 Calc(2,k-2)。

对于 dp(u,1)，要分类讨论：

1. 选择了环外子结点，那么 dp(u,1)+Calc(2,k-2)\to dp(u,1)；

2. 选择了 v_1，那么 dp(u,2)+dp(v_2,2)+dp(v_1,0)+Calc(4,k-2)；

3. 选择了 v_{k-1}，那么 dp(u,2)+dp(v_{k-2},2)+dp(v_{k-1},0)+Calc(2,k-4)。

代码，请勿直接抄袭：

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2000010;
int n,m,x,y,eg,ans,tot,h[MAXN],hd[MAXN],ver[2*MAXN],nx[2*MAXN],dfn[MAXN],low[MAXN],f[MAXN],dp[MAXN][3];
int rg[MAXN],tmp[MAXN][3];
void add_edge (int x,int y) {
    ver[++eg]=y;
    nx[eg]=hd[x];
    hd[x]=eg;
    return;
}
int get_dp (int l,int r) {
    tmp[l-1][0]=0,tmp[l-1][1]=dp[rg[l-1]][1],tmp[l-1][2]=dp[rg[l-1]][2];
    for (int i=l;i<=r+1;i++) {
        tmp[i][0]=tmp[i-1][2]+dp[rg[i]][0];
        tmp[i][2]=max(tmp[i-1][1],tmp[i-1][2])+dp[rg[i]][2];
        tmp[i][1]=max(tmp[i-1][0]+dp[rg[i]][2],max(tmp[i-1][1],tmp[i-1][2])+dp[rg[i]][1]);
    }
    //cout << l << "  " << r << "  " << max(tmp[r+1][1],tmp[r+1][2]) << endl;
    return max(tmp[r+1][1],tmp[r+1][2]);
}
void solve (int s,int t) {
    int cnt=0;
    rg[++cnt]=s;
    while (rg[cnt]!=t) {
        rg[cnt+1]=f[rg[cnt]];
        cnt++;
    }
    dp[t][1]=max(dp[t][1]+get_dp(2,cnt-2),dp[t][2]+max(dp[rg[1]][0]+dp[rg[2]][2]+get_dp(4,cnt-2),dp[rg[cnt-1]][0]+dp[rg[cnt-2]][2]+get_dp(2,cnt-4)));
    dp[t][0]+=get_dp(3,cnt-3)+dp[rg[1]][2]+dp[rg[cnt-1]][2];
    dp[t][2]+=get_dp(2,cnt-2);
    return;
}
void dfs (int x,int fa) {
    f[x]=fa,dfn[x]=low[x]=++tot,dp[x][0]=h[x],dp[x][2]=0;
    int tmp=0;
    for (int i=hd[x];i;i=nx[i]) {
        if (!dfn[ver[i]]) {
            dfs(ver[i],x);
            low[x]=min(low[x],low[ver[i]]);
        } else if (ver[i]!=fa) {
            low[x]=min(low[x],dfn[ver[i]]);
        }
        if (low[ver[i]]>dfn[x]) {
            dp[x][0]+=dp[ver[i]][2];
            dp[x][2]+=max(dp[ver[i]][2],dp[ver[i]][1]);
            tmp=max(tmp,dp[ver[i]][0]-max(dp[ver[i]][2],dp[ver[i]][1]));
        }
    }
    dp[x][1]=dp[x][2]+tmp;
    //cout << x << "  " << dp[x][0] << "  " << dp[x][1] << "  " << dp[x][2] << endl;
    for (int i=hd[x];i;i=nx[i]) {
        if (low[ver[i]]==dfn[x]&&f[ver[i]]!=x) {solve(ver[i],x);}
    }
    //cout << x << "  " << dp[x][0] << "  " << dp[x][1] << "  " << dp[x][2] << endl;
    return;
}
int main () {
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) {
        if (!dfn[i]) {
            dfs(i,0);
            ans+=max(dp[i][0],max(dp[i][1],dp[i][2]));
        }
    }
    printf("%d\n",ans);
    return 0;
}