首页 > 其他 > 详细

骑士(树形dp)

时间:2018-12-08 12:00:42      阅读:159      评论:0      收藏:0      [点我收藏+]

题意:给你一个基环树森林,每个点有一个权值,一条边上的两个节点不能同时选择。选取任意个节点,求最大权值和

 

对于每颗基环树:找环→断边→树形dp(没有上司的舞会)

 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1000005
#define LL long long
using namespace std;

inline int read()
{
    int f=1,x=0;
    char ch=getchar();
    while(ch<0 || ch>9) {if(ch==-) f=-1; ch=getchar();}
    while(ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
    return x*f;
}

int n,cnt=-1;
int val[MAXN];
int v[MAXN<<1],head[MAXN],nxt[MAXN<<1];
int k1,k2,e;
bool book[MAXN];
LL f[MAXN][2],nans,ans;

void add(int x,int y)
{
    v[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}

void find_circle(int x,int fa)
{
    book[x]=1; 
    for(int i=head[x];i!=-1;i=nxt[i])
    {
        int t=v[i];
        if(t==fa) continue;
        if(book[t])
        {
            k1=x;
            k2=t;
            e=i;
            continue;
        }
        find_circle(t,x);
    }
}

void dfs(int x,int fa)
{
    f[x][1]=val[x];
    f[x][0]=0;
    for(int i=head[x];i!=-1;i=nxt[i])
    {
        int t=v[i];
        if(i==e || (i^1)==e) continue;
        if(t==fa) continue;
        dfs(t,x);
        f[x][0]+=max(f[t][0],f[t][1]);
        f[x][1]+=f[t][0];
    }
}

int main()
{
    memset(head,-1,sizeof(head));
    int i;
    int x;
    n=read();
    for(i=1;i<=n;i++)
    {
        val[i]=read();
        x=read();
        add(i,x);
        add(x,i);
    }
    for(i=1;i<=n;i++)
    {
        if(!book[i])
        {
            find_circle(i,-1);
            dfs(k1,-1);
            nans=f[k1][0];
            dfs(k2,-1);
            nans=max(nans,f[k2][0]);
            ans+=nans;
        }
    }
    printf("%lld",ans);
    return 0;
}

 

骑士(树形dp)

原文:https://www.cnblogs.com/llllllpppppp/p/10086911.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!