BZOJ 1040 ZJOI 2008 騎士 基環樹林+樹形DP

BZOJ 1040 ZJOI 2008 騎士 基環樹林+樹形DP

題目大意：有一些騎士，他們每個人都有一個權值。但是由於一些問題，每一個騎士都特別討厭另一個騎士。所以不能把他們安排在一起。求這些騎士所組成的編隊的最大權值和是多少。

思路：首先貌似是有向圖的樣子，但是一個人討厭另一個人，他們兩個就不能在一起，所以邊可以看成是無向的。

n個點，n條無向邊，好像是一顆基環樹。但其實這是一個基環樹林，因為題中並沒有說保證圖一定聯通。

然後就可以深搜了，處理出每一個聯通塊。其實每一個聯通塊就是一個基環樹，在這個基環樹上進行樹形DP。求出最大值，然後累加到答案上。答案要開long long。

樹形DP具體的過程是，去掉一條邊，使這個基環樹變成一顆樹，然後進行正常的樹形DP。在環上任找一點，和與之相鄰的一點，標記他們之間的邊，在一會dp的時候不能經過這條邊，然後從選擇的第一個點dp。f[i]表示取這個點的時候最大的權值和，g[i]表示不取這個點的時候的最大權值和。

進行完dp後，取剛才選取的樹的根的g的值g[root]來更新答案。然後再對與它相鄰的點進行dp，用g[_root]來更新答案。

CODE：

#include 
#include 
#include 
#include 
#define MAX 1000010
using namespace std;

int points;
int src[MAX];
int head[MAX],total = 1;
int next[MAX << 1],aim[MAX << 1];

long long f[MAX],g[MAX],ans;
int root,_root;
bool v[MAX],found;
int not_pass;

inline void Add(int x,int y);
void DFS(int x,int last);
void TreeDP(int x,int last);

int main()
{
	cin >> points;
	for(int x,i = 1;i <= points; ++i) {
		scanf("%d%d",&src[i],&x);
		Add(i,x),Add(x,i);
	}
	for(int i = 1;i <= points; ++i)
		if(!v[i]) {
			DFS(i,-1);
			TreeDP(root,-1);
			long long temp = g[root];
			TreeDP(_root,-1);
			temp = max(temp,g[_root]);
			ans += temp;
		}
	cout << ans << endl;
	return 0;
}

inline void Add(int x,int y)
{
	next[++total] = head[x];
	aim[total] = y;
	head[x] = total;
}

void DFS(int x,int last)
{
	v[x] = true;
	for(int i = head[x];i;i = next[i]) {
		if(aim[i] == last)	continue;
		if(!v[aim[i]])	DFS(aim[i],x);
		else {
			not_pass = i;
			root = aim[i];
			_root = x;
		}
	}
}

void TreeDP(int x,int last)
{
	f[x] = src[x],g[x] = 0;
	for(int i = head[x];i;i = next[i]) {
		if(aim[i] == last)	continue;
		if(i == not_pass || i == (not_pass^1))	continue;
		TreeDP(aim[i],x);
		f[x] += g[aim[i]];
		g[x] += max(f[aim[i]],g[aim[i]]);
	}
}