M_sea

洛谷4244 [SHOI2008]仙人掌图
LuoguBZOJ分析和仙人掌最大独立集类似,不过难一些。设 $f[i]$ 表示 $i$ 子树中以 $i$ 为端点...
扫描右侧二维码阅读全文
17
2019/05

洛谷4244 [SHOI2008]仙人掌图

Luogu

BZOJ

分析

和仙人掌最大独立集类似,不过难一些。

设 $f[i]$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。

如果当前边是桥,直接转移,同时更新 $ans$ 。

否则当前边在环上,先不处理。


假设我们现在在 $u$ , $v$ 已经被访问过了。那么 $u$ 是这个环的底端, $v$ 是这个环的顶端。

我们把这个环找出来单独考虑。

先考虑怎么用环上的点更新答案。

要求的实际上是 $\max\{f[i]+f[j]+dis(i,j)\}$ ,这里的 $dis(i,j)=\min(|dep[i]-dep[j]|,sz-|dep[i]-dep[j]|)$ 。

维护一个单调队列,按照深度排序后一次进栈,这样子就去掉了绝对值。

因为是环,所以要倍长接在后面。

如果当前点与队头的深度差大于 $sz/2$ 了,那么就让队头出队即可。

然后再考虑怎么计算顶端的 $f$ 值。直接枚举环上的点更新即可。


应该比较容易理解。具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;
const int M=500000+10;

struct Edge { int v,nxt; } e[M];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int ans=0;
int dfn[N],low[N],tim=0;
int fa[N],dep[N],f[N];
int seq[N<<1],Q[N<<1];

inline void dp(int u,int v) { //环上的dp
    int tot=0,h=1,t=0;
    for (re int i=v;i!=u;i=fa[i]) seq[++tot]=i; seq[++tot]=u;
    reverse(seq+1,seq+tot+1);
    for (re int i=1;i<=tot;++i) seq[i+tot]=seq[i];
    for (re int i=1;i<=(tot<<1);++i) {
        while (h<=t&&i-Q[h]>tot/2) ++h;
        if (h<=t) ans=max(ans,f[seq[i]]+f[seq[Q[h]]]+i-Q[h]);
        while (h<=t&&f[seq[i]]-i>f[seq[Q[t]]]-Q[t]) --t;
        Q[++t]=i;
    }
    for (re int i=v;i!=u;i=fa[i])
        f[u]=max(f[u],f[i]+min(dep[i]-dep[u],dep[v]-dep[i]+1));
}

inline void tarjan(int u,int pa) {
    dfn[u]=low[u]=++tim;
    fa[u]=pa,dep[u]=dep[pa]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
        else if (v!=pa) low[u]=min(low[u],dfn[v]);
        if (low[v]>dfn[u]) ans=max(ans,f[u]+f[v]+1),f[u]=max(f[u],f[v]+1);
    }
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (u!=fa[v]&&dfn[u]<dfn[v]) dp(u,v);
    }
}

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int k=read(),u=read();
        for (re int j=1;j<k;++j) {
            int v=read();
            addEdge(u,v),addEdge(v,u);
            u=v;
        }
    }
    tarjan(1,0);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 03 PM

发表评论