题解 P2478 【[SDOI2010]城市规划】
一道仙人掌上 DP 的题。
首先是 Tarjan 找环,然后对环上 DP 和树上 DP 分别讨论:
设
树上 DP 部分:
设
而
环上 DP 部分:
计算环顶 DP 的值,设环顶为
先定义一个
对于
对于
对于
-
选择了环外子结点,那么
dp(u,1)+Calc(2,k-2)\to dp(u,1) ; -
选择了
v_1 ,那么dp(u,2)+dp(v_2,2)+dp(v_1,0)+Calc(4,k-2) ; -
选择了
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;
}