題目鏈接

1040: [ZJOI2008]騎士

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?3054??Solved:?1162
[Submit][Status][Discuss]

Description

Z國的騎士團是一個很有勢力的組織，幫會中匯聚了來自各地的精英。他們劫富濟貧，懲惡揚善，受到社會各界的贊揚。最近發生了一件可怕的事情，邪惡的Y國發動了一場針對Z國的侵略戰爭。戰火綿延五百里，在和平環境中安逸了數百年的Z國又怎能抵擋的住Y國的軍隊。于是人們把所有的希望都寄托在了騎士團的身上，就像期待有一個真龍天子的降生，帶領正義打敗邪惡。騎士團是肯定具有打敗邪惡勢力的能力的，但是騎士們互相之間往往有一些矛盾。每個騎士都有且僅有一個自己最厭惡的騎士（當然不是他自己），他是絕對不會與自己最厭惡的人一同出征的。戰火綿延，人民生靈涂炭，組織起一個騎士軍團加入戰斗刻不容緩！國王交給了你一個艱巨的任務，從所有的騎士中選出一個騎士軍團，使得軍團內沒有矛盾的兩人（不存在一個騎士與他最痛恨的人一同被選入騎士軍團的情況），并且，使得這支騎士軍團最具有戰斗力。為了描述戰斗力，我們將騎士按照1至N編號，給每名騎士一個戰斗力的估計，一個軍團的戰斗力為所有騎士的戰斗力總和。

Input

第一行包含一個正整數N，描述騎士團的人數。接下來N行，每行兩個正整數，按順序描述每一名騎士的戰斗力和他最痛恨的騎士。

Output

應包含一行，包含一個整數，表示你所選出的騎士軍團的戰斗力。

Sample Input

3
10 2
20 3
30 1

Sample Output

30

HINT

?

對于100%的測試數據，滿足N ≤ 1 000 000，每名騎士的戰斗力都是不大于?? 1 000 000的正整數。

根據題目可以知道， 每一個聯通塊里有且只有一個環， 所以我們找到這個環然后從中間把它斷開， 對斷開的兩個端點u1, u2, 分別dfs。 設dp[u][0]為不選u, dp[u][1]為選u， 那么答案就是max(dp[u1][0], dp[u2][0])。 注意有好多聯通塊， 一開始沒想到狂wa不止。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9+7;
const int inf = 1061109567;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int maxn = 1e6+5;
int head[maxn*2], num, u1, u2, a[maxn], vis[maxn], E;
ll dp[maxn][2];
struct node
{int to, nextt;
}e[maxn*2];
void add(int u, int v) {e[num].to = v, e[num].nextt = head[u], head[u] = num++;
}
void init() {num = 0;mem1(head);
}
void get_circle(int u, int from) {vis[u] = 1;for(int i = head[u]; ~i; i = e[i].nextt) {int v = e[i].to;if((i^1) == from)continue;if(vis[v]) {u1 = u, u2 = v;E = i;continue ;}get_circle(v, i);}
}
void dfs(int u, int from) {dp[u][1] = a[u];dp[u][0] = 0;for(int i = head[u]; ~i; i = e[i].nextt) {int v = e[i].to;if((i^1) == from)continue;if(i == E || (i^1)==E)continue;dfs(v, i);dp[u][1] += dp[v][0];dp[u][0] += max(dp[v][1], dp[v][0]);}
}
int main()
{int n, x;cin>>n;init();for(int i = 1; i<=n; i++) {scanf("%d%d", &a[i], &x);add(i, x);add(x, i);}ll ans = 0;for(int i = 1; i<=n; i++) {if(vis[i])continue;get_circle(i, -1);dfs(u1, -1);ll tmp = dp[u1][0];dfs(u2, -1);tmp = max(tmp, dp[u2][0]);ans += tmp;}cout<<ans<<endl;return 0;
}

?

轉載于:https://www.cnblogs.com/yohaha/p/5229775.html

總結

以上是生活随笔為你收集整理的bzoj 1040: [ZJOI2008]骑士 树形dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。