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

ydc的博客

 
 
 

日志

 
 

bzoj 1040(ZJOI2008) 骑士  

2013-02-27 21:00:30|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

做了三道环形DP的题,bzoj 1040骑士,bzoj 1023仙人掌啥的,还有就是hnoi2009的neverland了

我是先做过了1023,然后做neverland的时候就隐约觉得熟悉,然后去看题解,看标程。也正因为这样,由于两道题标程不是同一个人写的所以虽然过了这两道题我却反而两道题都有些不明白了

今天又看到了骑士这道题,于是回过头去看两道题的代码,对环形dp大概有了些想法吧

 

这三题都有个共同的特点:

①如果是树的话非常好做

②不是树……

③不过没关系,他的图非常特殊(似乎都是仙人掌图耶??)

好吧如果括号内的是错的误人子弟了还请吐槽轻点……

 

那这样的话,每条边要不然是桥,要不然可以乱搞一下

以骑士这道题为例,首先有向边要变为无向边是显然的啦……

然后如果我们遇到了一个环,那么请注意,由于图的特殊性,那条边应该只会出现在简单回路中一次

我们在做搜索的时候会得到一棵搜索树,环就相当于是一条链加一条回边了

假设回边叫做(v,u)也即v在搜索树中比u深,我们可以特殊处理一下

在bzoj 1023的题解中,我提到F[i][0],F[i][1]分别表示选/不选的最大值中还有个条件在一个环上,环上的点只用来转移环顶点的F值

那么我们强制v不选即可求出F[u][1]

求F[u][0]则和普通的没什么区别了

先贴一份自认为比较好懂的代码

如果有人觉得这和我写的别的环形DP的代码流程不一样产生了纠结,推荐以这份代码为准

因为这是我最后做的,自然我前面的总结也主要是针对这份代码

其他的代码……其实有的地方是在抄别人的

自己懂了但是可能和前面讲的有出入

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1000010
#define MAXM 2000010
#define x first
#define y second
using namespace std;
typedef long long LL;
LL F[MAXN][2];
int dfn[MAXN],low[MAXN],father[MAXN],num;
int n,value[MAXN];
int tot,to[MAXM],next[MAXM],start[MAXN];
void make(int a,int b){  tot++,to[tot]=b,next[tot]=start[a],start[a]=tot;  }
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
    Read(n);
    for(int i=1,a;i<=n;i++)
    {
        Read(value[i]),Read(a);
        make(i,a),make(a,i);
    }
}
void DFS(int p)
{
    dfn[p]=low[p]=++num,F[p][0]=0,F[p][1]=value[p];
    for(int i=start[p];i;i=next[i])
    {
        int q=to[i];
        if(dfn[q]==0)
        {
            father[q]=p,DFS(q);
            low[p]=min(low[p],low[q]);
            if(dfn[p]<low[q])  F[p][0]=F[p][0]+max(F[q][0],F[q][1]),F[p][1]=F[p][1]+F[q][0];
        }
        else if(dfn[q]<dfn[p]&&q!=father[p])  low[p]=min(low[p],dfn[q]);
    }
    for(int i=start[p];i;i=next[i])
        if(father[to[i]]!=p&&dfn[p]<dfn[to[i]])
        {
            int q=to[i];
            pair<LL,LL>power;
            power=make_pair(F[q][0],F[q][1]);
            for(int j=father[q];j!=p;j=father[j])
                power=make_pair(max(power.x,power.y)+F[j][0],power.x+F[j][1]);
            F[p][0]=F[p][0]+max(power.x,power.y);
            power=make_pair(F[q][0],-1000000000000000LL);
            for(int j=father[q];j!=p;j=father[j])
                power=make_pair(max(power.x,power.y)+F[j][0],power.x+F[j][1]);
            F[p][1]=F[p][1]+power.x;
        }
}
LL work()
{
    LL ans=0;
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)
        {
            DFS(i);
            ans=ans+max(F[i][0],F[i][1]);
        }
    return ans;
}
int main()
{
    read();
    cout<<work()<<endl;
    return 0;
}


  评论这张
 
阅读(968)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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