书海扬帆的博客

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$能得到的最大战斗力;

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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。
我现在还没有想出这种思路的正解呢…
大家认为行不行呢?



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:725.9k