注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1023 也即 poj 3567  

2013-02-04 21:31:13|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

PS:如果你再去看下我的bzoj1040骑士一题题解,相信能更明白我的意思

我们要发掘出每条边的信息:要不是桥,要不是一个环上的边。那么对于这两种特殊边我们可以如何处理呢?

我们用dfs遍历图,能得到一棵dfs树。进行树形dp,F[i]表示dfs树上,以i为根的子树上以i为起点的最长链。需要注意的是,我的代码中,如果p是在环上又不是环上的最高点(因为一个环上的每一个点在树上都有一个高度且必有一个最高),那么这个环上的路径不算在最长链中。如果是最高点则算,这里说的有些难理解,可以配合转移方程理解。

对于桥(u,v),用F[v]+F[u]+1更新ans(这个时候F[u]还未更新),然后用F[v]+1更新F[u]

对于环:首先注意到,由于图是仙人掌图,所以除了最高点以外的点,它们的F值只会影响到环上的点的F值,而不会影响到其他块块的点的F值(块块指的是把桥砍掉之后图剩下的若干个联通块),所以我们只要更新ans值和最高点F值即可。这也正是我上面讲的那句冗杂的话的意思。

F值可以O(环的个数)扫一边求得,这一部分总时间复杂度是O(n)的

更新ans值,我们发现枚举到i的时候,ans=max(ans,max{F[j]+dis(i,j))这就可以用经典的单调队列维护了。由于是环形,所以可以把链翻倍。

具体见程序

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define MAXN 50010
#define pb push_back
using namespace std;
int n,m,sum[MAXN],num,ans,F[MAXN],father[MAXN];
int dfn[MAXN],low[MAXN];
int a[MAXN*2],b[MAXN*2],queue[MAXN*2];
vector<int>edge[MAXN];
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1,k;i<=m;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
            scanf("%d",&a[j]);
        for(int j=1;j<k;j++)
            edge[a[j]].pb(a[j+1]),edge[a[j+1]].pb(a[j]);
    }
}
void Dp(int root,int p)
{
    int n=sum[p]-sum[root]+1,front=1,rear=1;
    for(int i=p;i!=root;i=father[i])
        a[n--]=F[i];
    a[n]=F[root],n=sum[p]-sum[root]+1;
    for(int i=n+1;i<=n+n;i++)
        a[i]=a[i-n];
    queue[front]=1;
    for(int i=2;i<=n+n/2;i++)
    {
        while(front<=rear&&queue[front]<i-n/2)  front++;
        ans=max(ans,a[front[queue]]+a[i]+i-queue[front]);
        while(front<=rear&&a[queue[rear]]-queue[rear]<=a[i]-i)  rear--;
        queue[++rear]=i;
    }
    for(int i=2;i<=n;i++)
        F[root]=max(F[root],a[i]+min(i-1,n-i+1));
}
void Tarjan(int p)
{
    dfn[p]=low[p]=++num;
    for(int i=0;i<edge[p].size();i++)
        if(edge[p][i]!=father[p])
        {
            int q=edge[p][i];
            if(dfn[q]==0)  father[q]=p,sum[q]=sum[p]+1,Tarjan(q);
            low[p]=min(low[p],low[q]);
            if(dfn[p]<low[q])  ans=max(ans,F[p]+F[q]+1),F[p]=max(F[p],F[q]+1);
        }
    for(int i=0;i<edge[p].size();i++)
        if(father[edge[p][i]]!=p&&dfn[p]<dfn[edge[p][i]])
            Dp(p,edge[p][i]);
}
int main()
{
    read();
    Tarjan(1);
    printf("%d\n",ans);
    return 0;
}


  评论这张
 
阅读(1806)| 评论(11)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017