[BZOJ1040][CODEVS1423][ZJOI2008]骑士

题目描述 Description

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

输入描述 Input Description

第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出描述 Output Description

应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

样例输入 Sample Input

10 2

20 3

30 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

之前的一些废话：是时候准备会考了。。

题解：

有点恶心的题。

解法1：首先考虑n个点n条边的连通图，如果是n个点n-1条边那就是一棵树，再加一条边就是一个环，环上再支出去一些小树，叫做无向环套外（内）向树。虽然这题的图不一定是连通的，但是由于每一个点只会支出去一条边，所以本图是由若干个无向环套外（内）向树组成的。对于一个无向环套外（内）向树，怎么做呢？对于树的话我们可以通过树形DP（类似没有上司的舞会）的做法来做，f(i,0)表示不取 f(i,1)表示取 f(i,1)=max{f(j,0)}+w[i] f(i,0)=max{f(j,0))},max{f(j,1)}但是涉及到环呢？其实也是类似的。只不过由于首尾是有影响的，所以我们需要先强制选首选和不选各做一次DP，然后取最优值。所以首先dfs扫出该联通块内的环，打标记。对于环上每一个点进行树形DP得到答案，然后在一个环上做DP得到答案。至于如何找环的话，我们需要dfs过程中记录一下前驱。然后由于有二元环的情况，不能简单的传fa，而是需要传边的编号。

解法2：这是我在打解法1时候无意间想到的，由于n个点n条边，少一个边就变成树了，然后就可以简单的树形DP了，于是我们在dfs找环的过程中如果找到了环上的一条边，于是我们把这条边砍掉，也就是树形DP时候不走这条边，做一次DP。但是由于还是有首尾不能同时选的原因，我们可以强行选一个点或不选各做一次，也可以分别取两个点都强制不取各做一次。仔细思考一番，发现选取后者代码复杂度更低，因为如果强行取的话需要在树形DP里特判，这样就比较麻烦了。

代码：

解法1：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

#define mem(a,b) memset(a,b,sizeof(a))

inline int read()

{

    int x=,f=;char c=getchar();

    while(!isdigit(c)){if(c=='-')f=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}

    return x*f;

}

const int maxn=;

struct Edge

{

    int u,v,next;

    Edge() {}

    Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {}

}e[maxn<<];

int n,a,ce=-,num,first[maxn],w[maxn],pre[maxn],vis[maxn],bl[maxn],tag[maxn],top[maxn],nxt[maxn];

bool ok;

LL ans,dp[][maxn],dp2[][maxn];

void addEdge(int a,int b)

{

    e[++ce]=Edge(a,b,first[a]);first[a]=ce;

    e[++ce]=Edge(b,a,first[b]);first[b]=ce;

}

void dfs(int now,int eid,int id)

{

    vis[now]=-;bl[now]=id;

    for(int i=first[now];i!=-;i=e[i].next)

        if(i!=eid)

        {

            if(vis[e[i].v]==-)

            {

                int tmp=now;tag[e[i].v]=id;top[id]=e[i].v;

                while(tmp!=e[i].v)tag[tmp]=id,tmp=pre[tmp];

            }

            else if(vis[e[i].v]==)pre[e[i].v]=now,dfs(e[i].v,i^,id);

        }

    vis[now]=;

}

void treeDP(int now,int fa,int id)

{

    dp[][now]=w[now];

    for(int i=first[now];i!=-;i=e[i].next)

        if(!tag[e[i].v] && e[i].v!=fa)

        {

            treeDP(e[i].v,now,id);

            dp[][now]+=dp[][e[i].v];

            dp[][now]+=max(dp[][e[i].v],dp[][e[i].v]);

        }

}

void loopinit(int now,int eid,int front,int id)

{

    if(!ok)treeDP(now,,id);

    for(int i=first[now];i!=-;i=e[i].next)

        if(tag[e[i].v]==id && i!=eid)

        {

            if(!ok)nxt[now]=e[i].v;

            if(e[i].v==front){ok=;return;}

            if(!ok)loopinit(e[i].v,i^,front,id);

        }

}

LL loopDP(int front,int id)

{

    loopinit(front,-,front,id);

    LL ret=;mem(dp2,);

    dp2[][front]=dp[][front];

    int i=front;

    do

    {

        if(nxt[i]==front)break;

        dp2[][nxt[i]]=max(dp2[][i],dp2[][i])+dp[][nxt[i]];

        dp2[][nxt[i]]=dp2[][i]+dp[][nxt[i]];

        i=nxt[i];

    }while(i!=front);

    ret=max(dp2[][i],dp2[][i]);

    mem(dp2,);dp2[][front]=dp[][front];

    i=front;

    do

    {

        if(nxt[i]==front)break;

        dp2[][nxt[i]]=max(dp2[][i],dp2[][i])+dp[][nxt[i]];

        dp2[][nxt[i]]=dp2[][i]+dp[][nxt[i]];

        i=nxt[i];

    }while(i!=front);

    ret=max(ret,dp2[][i]);

    ok=;

    return ret;

}

int main()

{

    mem(first,-);

    n=read();

    for(int i=;i<=n;i++)w[i]=read(),a=read(),addEdge(i,a);

    for(int i=;i<=n;i++)if(!vis[i])dfs(i,-,++num);

    mem(vis,);

    for(int i=;i<=num;i++)ans+=loopDP(top[i],i);

    printf("%lld\n",ans);

    return ;

}

解法2：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

#define mem(a,b) memset(a,b,sizeof(a))

inline int read()

{

    int x=,f=;char c=getchar();

    while(!isdigit(c)){if(c=='-')f=-;c=getchar();}

    while(isdigit(c)){x=x*+c-'';c=getchar();}

    return x*f;

}

const int maxn=;

struct Edge

{

    int u,v,next;

    Edge() {}

    Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {}

}e[maxn<<];

int n,a,ce=-,num,first[maxn],w[maxn],vis[maxn],bl[maxn],tag[maxn],top[maxn],nxt[maxn],st,ed,es;

LL ans,dp[][maxn],dp2[][maxn];

void addEdge(int a,int b)

{

    e[++ce]=Edge(a,b,first[a]);first[a]=ce;

    e[++ce]=Edge(b,a,first[b]);first[b]=ce;

}

void treeDP(int now,int fa,int eid)

{

    dp[][now]=w[now];

    for(int i=first[now];i!=-;i=e[i].next)

        if(i!=eid && (i^)!=eid && e[i].v!=fa)

        {

            treeDP(e[i].v,now,eid);

            dp[][now]+=dp[][e[i].v];

            dp[][now]+=max(dp[][e[i].v],dp[][e[i].v]);

        }

}

void dfs(int now,int eid,int id)

{

    vis[now]=-;

    for(int i=first[now];i!=-;i=e[i].next)

        if(i!=eid)

        {

            if(vis[e[i].v]==-)st=now,ed=e[i].v,es=i;

            else if(!vis[e[i].v])dfs(e[i].v,i^,id);

        }

    vis[now]=;

}

LL DP(int a,int b)

{

    mem(dp,);

    treeDP(a,,b);

    return dp[][a];

}

int main()

{

    mem(first,-);

    n=read();

    for(int i=;i<=n;i++)w[i]=read(),a=read(),addEdge(i,a);

    for(int i=;i<=n;i++)if(!vis[i])

    {

        dfs(i,-,++num);

        LL ret=max(DP(st,es),DP(ed,es));

        ans+=ret;st=ed=;es=-;

    }

    printf("%lld\n",ans);

    return ;

}

总结：

对于二元环一定要特殊考虑，传边的编号。
一定要关注代码复杂度。

巴特西

[BZOJ1040][CODEVS1423][ZJOI2008]骑士

最新文章

热门文章