about 4 years ago

学了好久调了好久……
仙人掌dp分成在环上和树上就好
但是有很多的细节要注意
论静态查错是多么的重要
代码还有一点小问题,sth大爷的数据没有全过。poj的还没试过
-------------------------update--------------------------------
fe是为了判断二元环而设的,但是此题二元环可直接当树边处理,没有影响。用fa判断即可
而且用fe会在sth的数据上wa3个点
但是sth用feA了自己的数据……
但是他的边从1开始……0.0不知道怎么异或找的相反边……
仙人掌最多有多少条边的计算一开始也不知道……poj mle。。
初步计算应该是最坏情况下是二元环,这样就是n*2条边,加上反向边4*n
代码中用fe的地方注释掉了换成了fa

于是冲到了pojrank1……

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define maxn 50001

#define maxm 200001

using namespace std;
int next[maxm],point[maxn],v[maxm];
int dfn[maxn],low[maxn],fe[maxn],f[maxn],fa[maxn];
int n,m,widen=-1,ans=0,tot=0;
int loop[maxn*2],ln=0,start,til;
struct node
{int num,pos;} q[maxn*2];
inline int readln()
{
    char c=getchar();int result=0,bj=1;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
inline void addedge(int x,int y)
{
    widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
    widen++;next[widen]=point[y];point[y]=widen;v[widen]=x;
}
void workonloop()
{
    int i,x;
    memcpy(loop+ln+1,loop+1,sizeof(int)*ln);
    q[1].pos=1;q[1].num=f[loop[1]]-1;
    start=1;til=1;
    for (i=2;i<=ln*2;i++)//注意下面所有都是环上的!!! 
    {
        for (;q[start].pos<i-(ln)/2;start++);
        ans=max(ans,q[start].num+f[loop[i]]+i);
        x=f[loop[i]]-i;
        for (;start<=til&&q[til].num<=x;til--);//会出现start>til的情况!! 
        q[++til].num=x;q[til].pos=i; 
    }
}
void dfs(int x)
{
    dfn[x]=low[x]=++tot;
    for (int k=point[x];k!=-1;k=next[k])
    if (fa[x]!=v[k])
//  if ((k^1)!=fe[x])                                                                                                                                                                                                                                         
    {
    if (dfn[v[k]])
        low[x]=min(low[x],dfn[v[k]]);
    else 
    {
        fe[v[k]]=k;fa[v[k]]=x;dfs(v[k]);
        low[x]=min(low[x],low[v[k]]);
    }
    }
    for (int k=point[x];k!=-1;k=next[k])
    if (fa[x]!=v[k])
//  if ((k^1)!=fe[x])
    {
        if (low[v[k]]>dfn[x])//在以x为根的子树里 
        {
            ans=max(ans,f[x]+1+f[v[k]]);
            f[x]=max(f[x],f[v[k]]+1);
        }
        else
        if (fa[v[k]]!=x&&dfn[x]<dfn[v[k]])
        //if (fe[v[k]]!=k&&dfn[x]<dfn[v[k]])//非树边且x点是靠上的点 
        {
            ln=0;int now=v[k];
            for (;x!=now;now=fa[now])
                loop[++ln]=now;
            loop[++ln]=x;
            workonloop();
            for (int i=1;i<ln;i++)
                f[x]=max(f[x],f[loop[i]]+min(i,ln-i));
        }
    }
}
int main()
{
    int i,j,k,x,y;
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    n=readln();m=readln();
    for (i=1;i<=m;i++)
    {
        k=readln();x=readln();
        for (j=1;j<k;j++,x=y)
        {
            y=readln();
            addedge(x,y);
        }
    }
    dfs(1);
    printf("%d\n",ans);
}
← 【bzoj2594】【lct】水管局长数据加强版 【bzoj3720】【块状树】gty的妹子树 →
 
comments powered by Disqus