程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 1655 樹形dp

poj 1655 樹形dp

編輯:關於C++

題意相當於給你一棵樹 讓你求每個點的不同子樹上的節點個數吧 注意存邊的時候存雙向邊

 

 

#include
#include
#include
using namespace std;

struct node
{
	int to,next;
}A[40010];
int tot,list[20010],mark[20010],n;
int add(int a,int b)
{
	A[++tot].to = b;            
   	A[tot].next = list[a]; 
   	list[a] = tot; 
 	return 0; 
}
int dp[20010],subtree[20010];
int max(int a,int b)
{
	return a>b?a:b;
}
int dfs(int point)
{
	mark[point]=1;
	int b;
	int k=list[point];
	if(k==-1) {dp[point]=n-1;subtree[point]=0;return 0;}
	for(;k!=-1;k = A[k].next) 
   	{
	   	b = A[k].to;
	   	if(mark[b]) continue;
	   	dfs(b);
	   	subtree[point]+=subtree[b]+1;
	   	dp[point]=max(dp[point],subtree[b]+1);
   	}
   	dp[point]=max(dp[point],n-subtree[point]-1);
   	return 0;
	
}
int main()
{
	int i,j,T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		tot=1;
		memset(list,-1,sizeof(list));
		memset(mark,0,sizeof(mark));
		for(i=1;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved