【樹形動态規劃】poj1463 strategic game

說白了，和一般的動态規劃也沒啥差別，隻不過是狀态的轉移跑到了樹的子父節點之間。

這道題目應該還算是簡單的，由于是第一次做，還是花費了很大的時間啊……

主要就是鄰接表表示圖（發現vector真的很好用，不用自己去寫連結清單嗷嗷嗷~），以及深度搜尋，在回溯是為了避免重複計算，用數組記錄下了中間的計算結果，這也應該是最展現動态規劃的一個地方吧。

輸入輸出用的比較混亂，還請大家輕拍~

#include<stdio.h>
#include<vector>
#include<iostream>
#define min(a,b) (a<b)?a:b
using namespace std;
int dfs(int order,int pr);
vector<int> edge[1501];
int num[1501][2];
int main(){
	int t,x,y,n;
	//int num[1501][2];
	while(cin>>t){
		//将上一個邊表清空 
		for(int i=0;i<t;i++)
			edge[i].clear();
		for(int i=0;i<t;i++){
			scanf("%d:(%d)",&x,&n);
			while(n--){ 
				scanf("%d",&y);
				edge[x].push_back(y);
				edge[y].push_back(x);
			} 
		}
		//為根節點構造一個虛拟的父節點 
		dfs(0,-1);
		cout<<(int)(min(num[0][0],num[0][1]))<<endl;
	}
	//system("pause");
	return 0;
}

int dfs(int order,int pr){
	int tmp;
	if(edge[order].size()==0){
		num[order][0]=0;
		num[order][1]=1;
		return 0;
	}
	//初始化為零 
	num[order][0]=num[order][1]=0;
	for(int i=0;i<edge[order].size();i++){
		tmp=edge[order][i];
		//對于父節點的情形不予考慮 
		if(tmp==pr)
			continue;
		dfs(tmp,order);
		//根節點空白則各子樹的根節點必須填充 
		num[order][0]+=num[tmp][1];
		//根節點填充則各子樹可填充或空白，選小者即可 
		num[order][1]+=min(num[tmp][0],num[tmp][1]);
	}
	num[order][1]++;
	return 0;
}