【BZOJ-1952】城市规划 [坑题] 仙人掌DP + 最大点权独立集（改）

1952: [Sdoi2010]城市规划

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 73 Solved: 23
[Submit][Status][Discuss]

Description

小猪iPig来到了一个叫做pigsty的城市里，pigsty是一座专门为小猪所准备的城市，城市里面一共有n个小区给小猪们居住，并且存在许多条无向边连接着许多小区。因为这里是一个和谐的城市，所以小猪iPig准备在这个城市里面度过他的余生。若干年之后小猪iPig当上了规划局长，这件事令他非常开心。不过与此同时pigsty城市里面出现了许多反和谐主义者，他们已经厌烦了这样和谐的生活，在城市里到处闹事。小猪iPig为了更好地控制局面，他把城市改造成了另外一个样子：iPig把道路全部摧毁之后重新修建了m条无向边，并且保证每一个小区最多存在于一个由无向边组成的环中。 iPig以为这样做就让那些反和谐主义者不敢继续猖狂下去了，谁知到在新的城市道路修建好以后反和谐主义者宣言要对城市的小区进行一次洗脑！这下可麻烦了，iPig赶紧收集了许多的情报。iPig给每个小区标记了一个和谐值HX_i，用它来表示第i个小区的和谐程度。通过地下消息iPig又得知那些反和谐主义者进攻时有个规律：他们会选择若干个小区下手，这些小区都派一只猪过去，把这些小区的和谐值归零。在这个过程中，每个选择的小区所直接连接着的几个小区都派了一只猪去看守——以防被警猪给干扰。这个计划看似完美但是还是存在一个漏洞：因为人员之间都是在网络上认识的，互相没有见过面，为了防止不必要的麻烦（认错猪之类），每个小区最多只会有一头猪存在。 iPig突然感到了莫大的压力，他想知道在最坏情况下会丢失多少和谐值。但是不懂计算机的他不知道应该怎样计算。你能帮帮他吗？

Input

输入第一行有两个整数n和m，表示pigsty城市里面有n个小区，在iPig修整城市后有m条无向边连接着n个小区。接下来一行有n个正整数，第i个正整数HX_i表示第i个小区的和谐值为HX_i。接下来m行，每行两个正整数a和b（1<=a,b<=n），表示存在一条连接着小区a和小区 b的无向边。

Output

输出只有一行一个整数，表示最坏情况下损失的和谐值为多少。

Sample Input

9 9
2 2 3 4 1 2 3 10 11
1 2
2 3
1 3
3 5
5 4
5 6
4 7
6 7
8 9

Sample Output

17

【样例解释】
反和谐主义者选择的小区分别是小区3（看守的小区是小区1、小区2和小区5）、小区7（看守的小区是小区4和小区6）和小区9（看守的小区是小区8），这样会损失的总和谐值为3+3+11=17。
或者选择的小区分别是小区1（看守的小区是小区2和小区3）、小区4（看守的小区是小区5和小区7）和小区9（看守的小区是小区8），这样会损失的总和谐值为2+4+11=17。
如果同时选择小区3、小区4和小区9，虽然损失的总和谐值为18，但是小区3和小区4都要派猪来看守小区5，这不符合条件，故此方案不可行。

【数据约定】
对于20%的数据，保证每个点不存在于任何一个环中；
对于另外30%的数据，保证图中只存在一个环；
对于100%的数据，有N<=1000000，M<=2000000，所有的权值不超过1000。

HINT

Source

Solution

这是一道坑题，测试数据有误，标算有误，所以想要AC需要和标算错的一样详见Discuss

询问了AC此题的Claris，得到的回复是：

说说正确做法：

仍旧是仙人掌DP，这里的话是仙人掌森林，不过原理是一样的e

求解最大点权独立集，然后仔细读样例发现，这里的“独立集”不同于平常的独立集，即不能选中间隔着一个的两个点

那么对于正常的求解方法是dp[i][0/1]表示当前到i位，选或不选的答案，这里就带限制的dp[i][0/1/2]去进行dp即可，转移是类似的

对仙人掌的处理方法一样是找环，拆环单独DP

Code

这里提供自己的正确做法（WA3组（数据有误）AC其余）

除discuss中提及的3组全A，并与提及的3组的正确答案相吻合

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define maxn 1000100
struct EdgeNode{int to,next;}edge[maxn<<2];
int head[maxn],cnt;
void add(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
void insert(int u,int v) {add(u,v); add(v,u);}
int deep[maxn],fa[maxn],dfn[maxn],low[maxn],dp1[maxn][3],dp2[maxn][3],ring[maxn],HX[maxn],t;
int n,m,ans;

void CactusDP(int st,int tt)
{
    ring[1]=tt; int zz=1;
    while (ring[zz]!=st) {ring[zz+1]=fa[ring[zz]]; zz++;}
    //printf("Num=%d  :",zz);
    //for (int i=1; i<=zz; i++) printf("%d ->",ring[i]); printf("
");
    int f0=0,f1=0,f2=0;
    for (int opt=0; opt<=2; opt++)
        {
            dp2[1][0]=dp2[1][1]=dp2[1][2]=0;
            dp2[1][opt]=dp1[tt][opt];
            if (opt==2) dp2[1][1]=dp2[1][2];
            for (int i=2; i<=zz; i++)
                dp2[i][0]=dp2[i-1][2]+dp1[ring[i]][0],
                dp2[i][1]=max(max(dp2[i-1][1],dp2[i-1][0])+dp1[ring[i]][2],dp2[i-1][1]+dp1[ring[i]][1]),
                dp2[i][2]=max(dp2[i-1][1],dp2[i-1][2])+dp1[ring[i]][2];
            if (opt==0) f1=max(f1,dp2[zz][2]);
            if (opt==1) f1=max(f1,dp2[zz][1]),f2=max(f2,dp2[zz][2]);
            if (opt==2) f1=max(f1,dp2[zz][1]),f0=max(f0,dp2[zz][0]),f2=max(f2,dp2[zz][2]);            
        }
    dp1[st][0]=f0; dp1[st][1]=f1; dp1[st][2]=f2;
}

void TreeDP(int now)
{
    dfn[now]=low[now]=++t; 
    dp1[now][2]=0; dp1[now][0]=HX[now]; int maxx=0;
    for (int i=head[now]; i; i=edge[i].next)
        if (edge[i].to!=fa[now])
            {
                if (deep[edge[i].to]) {low[now]=min(dfn[edge[i].to],low[now]); continue;}
                fa[edge[i].to]=now; deep[edge[i].to]=deep[now]+1;
                TreeDP(edge[i].to);
                if (low[edge[i].to]>low[now])
                    dp1[now][2]+=max(dp1[edge[i].to][1],dp1[edge[i].to][2]),
                    dp1[now][0]+=dp1[edge[i].to][2],
                    maxx=max(maxx,dp1[edge[i].to][0]-max(dp1[edge[i].to][1],dp1[edge[i].to][2]));
                low[now]=min(low[now],low[edge[i].to]);
            }
    dp1[now][1]=maxx+dp1[now][2];
    for (int i=head[now]; i; i=edge[i].next)
        if (low[edge[i].to]==dfn[now] && edge[i].to!=fa[now] && deep[edge[i].to]!=deep[now]+1)
            CactusDP(now,edge[i].to);
}

void Freopen() {freopen("area.in","r",stdin); freopen("area.out","w",stdout);}
void Fclose() {fclose(stdin); fclose(stdout);}

int main()
{
    //Freopen();
    n=read(),m=read();
    for (int i=1; i<=n; i++) HX[i]=read();
    for (int u,v,i=1; i<=m; i++) u=read(),v=read(),insert(u,v);
    for (int i=1; i<=n; i++) if (!dfn[i]) {fa[i]=i,deep[i]=1; TreeDP(i); ans+=max(dp1[i][0],max(dp1[i][1],dp1[i][2]));}
    printf("%d
",ans);
    //Fclose();
    return 0;
}

以及可A的标程，显然标程的判环是有些问题的

#include <cstdio> 
#include <cstring> 
#include <vector> 
#include <algorithm> 
using namespace std; 
   
const int N = 1000500, inf = ~0U >> 1; 
   
#define forEdges(iter,u) for(edge* iter = e[u]; iter; iter = iter->n) 
struct edge { int t; edge *n; } 
    ebf[N << 2], *e[N], *ec = ebf; 
   
int weight[N], n; 
int dfn[N], low[N], S[N], sTop, dTime; 
int f[N][3], rf[N][3], id[N], opt[N]; 
   
inline void updateN (int &x, int y) { if (x > y) x = y; } 
inline void updateX (int &x, int y) { if (x < y) x = y; } 
   
inline void dfs (int u, int au) 
{ 
    int v; 
    dfn[u] = low[u] = ++dTime, S[++sTop] = u; 
    forEdges(it, u) if ((v = it->t) != au) 
        if (!dfn[v]) dfs(v, u), updateN(low[u], low[v]); 
        else updateN(low[u], dfn[v]); 
    int maxDelt(0); 
    f[u][2] = 0, f[u][0] = weight[u]; 
    forEdges(it, u) if ((v = it->t) != au && low[v] > dfn[u]) // Sons 
    { 
        f[u][2] += max(f[v][1], f[v][2]); 
        f[u][0] += f[v][2]; 
        updateX(maxDelt, f[v][0] - max(f[v][1], f[v][2])); 
    } 
    f[u][1] = f[u][2] + maxDelt; 
       
    forEdges(it, u) if (low[it->t] == dfn[u]) // A ring 
    { 
        int rs = 0; 
        while (S[sTop] != u) id[++rs] = S[sTop--]; 
        id[++rs] = u; 
        /* RingDP : Line 53 .. 55 */
        int f0 = 0, f1 = 0, f2 = 0; 
        for (int st = 0; st <= 2; ++st) 
        { 
            rf[1][0] = rf[1][1] = rf[1][2] = 0; 
            rf[1][st] = f[id[1]][st]; 
            if (st == 2) rf[1][1] = rf[1][2]; 
            for (int i = 2; i <= rs; ++i) 
            { //RingDP 
                rf[i][0] = f[id[i]][0] + rf[i - 1][2]; 
                rf[i][1] = max(f[id[i]][2] + max(rf[i - 1][0], rf[i - 1][1]), f[id[i]][1] + rf[i - 1][1]); 
                rf[i][2] = f[id[i]][2] + max(rf[i - 1][1], rf[i - 1][2]); 
            } 
            switch (st) 
            { 
                case 0 : updateX(f1, rf[rs][2]); break; //!! 
                case 1 : updateX(f1, rf[rs][1]), updateX(f2, rf[rs][2]); break; 
                case 2 : updateX(f0, rf[rs][0]), updateX(f1, rf[rs][1]), updateX(f2, rf[rs][2]); break; 
            } 
        } 
        f[u][0] = f0, f[u][1] = f1, f[u][2] = f2; 
    } 
       
    if (dfn[u] == low[u]) while (S[sTop + 1] != u) --sTop; 
    opt[u] = max(f[u][0], max(f[u][1], f[u][2])); 
} 
   
int main () 
{ 
    int m, a, b; 
   // freopen("area.in", "r", stdin); 
   // freopen("area.out", "w", stdout); 
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= n; ++i) scanf("%d", weight + i); 
    while (m--) 
    { 
        scanf("%d%d", &a, &b); 
        *ec = (edge){b, e[a]}; e[a] = ec++; 
        *ec = (edge){a, e[b]}; e[b] = ec++; 
    } 
    int res = 0; 
    for (int i = 1; i <= n; ++i) 
        if (!dfn[i]) dfs(i, 0), res += opt[i]; //A Connected Component 
    printf("%d
", res); 
    return 0; 
}

std

开荒做这种大坑，简直了= =||