[树形dp, 基环树]ZJOI2008 骑士

BZOJ1040/洛谷P2607

描述

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

输入

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

输出

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

输入样例 1

3
10 2
20 3
30 1

输出样例 1

30

提示

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

解题思路

本题是一道树形dp的好题。

转化问题的方式

我们注意到,输入数据给出的是一个n个点,n条边的无向图,而并非一棵n个点,(n-1)条边的树。
事实上,数据给定的图称作一棵基环树,它只要去掉任意一条边,就可以变成一棵树。

换言之…

我们只需要去掉一条边,然后就变为了树形dp。
那么去掉哪一条呢?
我们需要枚举一下。

状态转移方程

$dp[u][0]$表示不选节点$u$能得到的最大战斗力;
$dp[u][1]$表示选节点$u$能得到的最大战斗力;

dp[u][0] = \sum\limits_{\left( {u,v} \right) \in E} {\max \left\{ {dp[v][1],dp[v][0]} \right\}}.
dp[u][1] = \sum\limits_{\left( {u,v} \right) \in E} {dp[v][0]}.

一遍dfs就可以得到dp数组的值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1e-8;
const int INF=2147483647;
typedef long long ll;
#define rg register
inline ll read() {
    rg ll x=0;char c=' ';while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x;
}
inline void print(rg ll x) {
    rg ll y=10,len=1;while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+'0');x%=y;}
}
const int maxn=1000100,maxm=2000200;
struct node {
    int v;
    node *next;
}*h[maxn],pool[maxm];
int edgecnt;
inline void addEdge(rg int u,rg int v) {
    rg node *p=&pool[++edgecnt];
    p->v=v;p->next=h[u];h[u]=p;
} 
inline void insert(rg int u,rg int v) {
    addEdge(u,v);addEdge(v,u);
}
int n,cnt;
ll dp[maxn][2],f[maxn],w[maxn],hate[maxn];
ll cur,ans;
//dp[i][0]表示不选 dp[i][1]表示选
//w表示点权 hate表示痛恨的人 
int remove_u[maxn],remove_v[maxn];
inline void init() {
    for(rg int i=1;i<=n;i++) f[i]=i;
}
inline int find(rg int x) {
    return f[x]==x?x:f[x]=find(f[x]);
}
inline void merge(rg int x,rg int y) {
    f[find(x)]=find(y);
}
inline void dfs(rg int u,rg int fa) {
    dp[u][1]=w[u];dp[u][0]=0;
    for(rg node *p=h[u];p;p=p->next) {
        rg int v=p->v;
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0]+=max(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main() {
    n=read();
    init();
    for(rg int i=1;i<=n;i++) {
        w[i]=read();hate[i]=read();
        if(find(i)!=find(hate[i])) {
            insert(i,hate[i]);
            merge(i,hate[i]);
        }
        else remove_u[++cnt]=i,remove_v[cnt]=hate[i];
    } 
    for(rg int i=1;i<=cnt;i++) {
        dfs(remove_u[i],0);
        cur=dp[remove_u[i]][0];
        dfs(remove_v[i],0);
        cur=max(cur,dp[remove_v[i]][0]);
        ans+=cur;
    }
    print(ans);
    return 0;
}

关于题目的新的思考

隔壁班神犇说可以用拓扑排序找环,然后进行拓扑序dp。
我现在还没有想出这种思路的正解呢…
大家认为行不行呢?

点赞

发表评论