【POJ1655】Balancing Act(树型动态规划)(POJ2378买一送一)

Categories: 数据结构和算法
Tags: No Tags
Comments: No Comments
Published on: 2011 年 05 月 05 日

struct Tree{
int sonnum;
int maxnode;
vector sons;
}trees[maxlen];
sonnum记录的是包含其节点自身的总孩子数。
maxnode记录的是山区该节点剩余的森林中,最大子树的节点数。
vector里存储子数的节点。
用一个深搜获得各项数据,详细请看代码。
这个题跟2378买一送一。。。改改输入输出即可。

#include <cstdio>
#include <vector>
using namespace std;
#define  maxlen 20002
struct Tree{
	int sonnum,maxnode;
	vector<int> sons;
}trees[maxlen];
int n,m,a,b,res,pos;
void init(int m){
	for (int i=0;i<=m;i++){
		trees[i].sonnum=trees[i].maxnode=0;
		trees[i].sons.clear();
	}
}
int dfs(int node,int father){
	int sonnum;
	trees[node].sonnum=1;
	trees[node].maxnode=0;
	for (int i=0;i<trees[node].sons.size();i++)
	{
		if(trees[node].sons[i]!=father)
		{
			sonnum=dfs(trees[node].sons[i],node);
			trees[node].sonnum+=sonnum;
			if(sonnum>trees[node].maxnode)
				trees[node].maxnode=sonnum;
		}
	}
	if((m-trees[node].sonnum)>trees[node].maxnode)
		trees[node].maxnode=(m-trees[node].sonnum);
	return trees[node].sonnum;
}
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d",&m);
		init(m);
		for(int i=0;i<m-1;i++){
			scanf("%d%d",&a,&b);
			trees[a].sons.push_back(b);
			trees[b].sons.push_back(a);
		}	
		dfs(1,0);
		res=maxlen+1,pos=0;
		for (int i=1;i<=m;i++)
			if(trees[i].maxnode<res){
				res=trees[i].maxnode;pos=i;
			}
		printf("%d %d\n",pos,res);
	}
}

2378输出格式,输入格式自己改吧。。。
for (int i=1;i<=m;i++) if(trees[i].maxnode<=(m/2)){ printf("%d\n",i); } [sr]

最多留言日志

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日