在仙人掌图上dp的处理 BZOJ1023+BZOJ1487

青旅半醒 2022-05-17 05:46 113阅读 0赞

仙人掌图就是图中包含圈，但是圈不能共边。举个例子， 如下图1、2、3：

![70][]![70 1][]![70 2][]

假如将这些圈的都缩成点，显然就是一棵树了，对于一棵树进行dp，那就很简单了。

因此，处理这类问题需要分两步。

1.当dp的边是桥，也就是不是环上的边，那我们就正常的从他的孩子中取最优解转移到该节点。

2.当dp的边是在环上。我们需写一个函数对该环单独处理，处理完成后将该环的信息更新到该环的入点（就是dfs时该环中最先访问的点）。这样该环的父节点只需要找这个入点就能对他进行更新。

对于1023这道求仙人掌直径的题。我们可以从任意一个节点跑tarjan（也就是深搜），设该点是u， 下一个点是v

1.如果dfn\[u\]<low\[v\]，说明这条边是树边（不是环上的边），所以先进行答案（直径）更新，![ans=max(ans,dp\[u\]+dp\[v\]+1)][ans_max_ans_dp_u_dp_v_1]，dp\[x\]是以x为根节点，到叶子节点的最长路径。再进行u点的更新 ![dp\[u\]=max(dp\[u\], dp\[v\]+1)][dp_u_max_dp_u_ dp_v_1]

2.如果dfn\[u\]<dfn\[v\] && fa\[v\]!=u,就是说他的孩子的父亲不是他（^\_^）。说明u，v在环上，u是环的入点，v是环最后一个点。

这时候需要将这个环上的点按顺序全保存到一个数组，然后再复制一半加到数组末尾。原因就是，我们要将所有的情况都考虑到。如下图所示。

![70 3][]

假如说我们从1号节点进入的，我们要看看ans=max(ans, dp\[i\]+dp\[j\]+dis(i, j)), 所以，i，j是环上的任意两对，存1.5倍的话计算就容易了，我们只需要用一个单调栈，维护栈中的点距离不超过cc/2的大小以及一个最长链。最后还要更新一下如节点。具体见代码。

#include<bits/stdc++.h>
    using namespace std;
    const int N=5e4+10;
    int n, m;
    vector<int> G[N];
    int dp[N], ans=0, dfn[N], low[N], a[N<<1], cnt=0, fa[N], dpth[N];
    int q[N<<1], rear, head;
    
    void cal_cir(int fir, int las){//处理环
    
        int cc=dpth[las]-dpth[fir]+1;
        int now=las;
    
        while(now!=fir) a[cc--]=dp[now], now=fa[now];//要用一个数组保存下来
    
        a[1]=dp[fir];
        cc=dpth[las]-dpth[fir]+1;
        for(int i=1; i<=cc>>1; i++) a[cc+i]=a[i];
        rear=head=0;
        q[rear++]=1;
        int up=cc+cc/2;
        for(int i=2; i<=up; i++){
            while(head<rear && i-q[head]>cc/2) head++;
            ans=max(ans, a[q[head]]+a[i]+i-q[head]);
    
            while(head<rear && a[i]>=a[q[rear-1]]+i-q[rear-1]) rear--;
            q[rear++]=i;
        }
        for(int i=2; i<=cc; i++)
            dp[fir]=max(dp[fir], a[i]+min((i-1), cc-i+1));
    }
    
    void tarjin(int x, int f){
        dfn[x]=low[x]=++cnt; fa[x]=f;
    
        for(int i=0; i<G[x].size(); i++){
            int to=G[x][i];
    
            if(to==fa[x]) continue;
            if(!dfn[to]) dpth[to]=dpth[x]+1, tarjin(to, x), low[x]=min(low[x], low[to]);
            else    low[x]=min(dfn[to], low[x]);
            if(low[to]>dfn[x])
                ans=max(ans, dp[to]+dp[x]+1), dp[x]=max(dp[x], dp[to]+1);//树边更新
        }
        for(int i=0; i<G[x].size(); i++){
            int to=G[x][i];
            if(dfn[x]<dfn[to] && fa[to]!=x)
                cal_cir(x, to);
        }
    
    }
    
    int main(){
        scanf("%d%d", &n, &m);
        int k;
        int u, v;
        for(int i=1; i<=m; i++){
            scanf("%d", &k);
            scanf("%d", &u);
            for(int j=2; j<=k; j++){
                scanf("%d", &v);
                G[u].push_back(v); G[v].push_back(u);
                u=v;
            }
        }
    
        tarjin(1, -1);
    
        printf("%d\n", ans);
        return 0;
    }

1487这个题跟直径是一个模式，都是 tarjan，处理环。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+10;
    struct Edg{
        int to, nxt;
    }e[N<<1];
    int cnt=0, head[N];
    void addEdg(int u, int v){
        e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt;
    }
    int val[N];
    int n, m, dfs_clock=0, dfn[N], dp[N][2], dpth[N], a[N][2], low[N], fa[N];
    
    void cal_cir(int fir, int las){
        int cc=dpth[las]-dpth[fir]+1;
        int now=las;
    
        while(now!=fir) a[cc][0]=dp[now][0], a[cc--][1]=dp[now][1], now=fa[now];
        a[1][0]=dp[fir][0]; a[1][1]=dp[fir][1];
        cc=dpth[las]-dpth[fir]+1;
    
        for(int i=cc-1; i>=1; i--){//入点必须选，会影响最后一个点
            if(i==cc-1)
                a[i][0]+=a[i+1][0];
            else
                a[i][0]+=max(a[i+1][0], a[i+1][1]);
            a[i][1]+=a[i+1][0];
        }
    
        dp[fir][1]=max(dp[fir][1], a[1][1]);
    
        now=las;
        while(now!=fir) a[cc][0]=dp[now][0], a[cc--][1]=dp[now][1], now=fa[now];
        a[1][0]=dp[fir][0]; a[1][1]=dp[fir][1];
        cc=dpth[las]-dpth[fir]+1;
    
        for(int i=cc-1; i>=1; i--){//入点不选
            a[i][0]+=max(a[i+1][1], a[i+1][0]);
            a[i][1]+=a[i+1][0];
        }
    
        dp[fir][0]=max(dp[fir][0], a[1][0]);
    }
    
    void tarjan(int x, int f){
        dp[x][1]=val[x];
        dfn[x]=low[x]=++dfs_clock;
        fa[x]=f;
        for(int i=head[x]; i; i=e[i].nxt){
            int to=e[i].to;
            if(to==f) continue;
            if(!dfn[to]) dpth[to]=dpth[x]+1, tarjan(to, x), low[x]=min(low[x], low[to]);
            else    low[x]=min(low[x], dfn[to]);
            if(dfn[x]<low[to])
                dp[x][1]+=dp[to][0], dp[x][0]+=max(dp[to][1], dp[to][0]);
        }
    
        for(int i=head[x]; i; i=e[i].nxt){
            int to=e[i].to;
            if(dfn[x]<dfn[to] && fa[to]!=x)
                cal_cir(x, to);
        }
    
    }
    
    int main(){
        scanf("%d%d", &n, &m);
        int u, v;
        for(int i=1; i<=m; i++){
            scanf("%d%d", &u, &v);
            addEdg(u, v); addEdg(v, u);
        }
        for(int i=1; i<=n; i++)
            scanf("%d", val+i);
    
        tarjan(1, -1);
    
        printf("%d\n", max(dp[1][0], dp[1][1]));
    
        return 0;
    }

[70]: https://img-blog.csdn.net/20180807153253286?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R1X2x1bg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180807153745767?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R1X2x1bg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220517/24e031707ac743259689e287ecb8bf89.png
[ans_max_ans_dp_u_dp_v_1]: https://private.codecogs.com/gif.latex?ans%3Dmax%28ans%2Cdp%5Bu%5D&plus;dp%5Bv%5D&plus;1%29
[dp_u_max_dp_u_ dp_v_1]: https://private.codecogs.com/gif.latex?dp%5Bu%5D%3Dmax%28dp%5Bu%5D%2C%20dp%5Bv%5D&plus;1%29
[70 3]: /images/20220517/14a444c9739249b988975c4e2e7c393b.png