pku 3398 递推.txt

NUAA ACM OJ源码

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3398 递推
#define NMAX 10005
#define CMAX 103
#define INFI 99999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

typedef struct ooparc
{
	int first;
	int second;
}ooparc;

typedef struct oopnode
{
	int fa;
	vector <int> child;
	int isdi;
	int from;
	int to;
}oopnode;

ooparc arc[NMAX*2];
oopnode node[NMAX];

int get_f0(int);
int get_f1(int);
int get_f2(int);

bool cmp(ooparc a,ooparc b)
{
	return a.first<b.first;
}

int getmin(int a,int b) {return a<b?a:b;}

void print_tree(int num)
{
	int i;
	vector <int>::iterator pp;
	for(i=1;i<=num;i++)
	{
		printf("it's %d(%d):",i,node[i].isdi);
		for(pp=node[i].child.begin();pp!=node[i].child.end();pp++)
			printf("%d ",*pp);
		printf("\n");
	}
}
void make_tree(int root)
{
	int i,w;
	bool flag=true;
	for(i=node[root].from;i<=node[root].to;i++)
	{
		w=arc[i].second;
		if(node[w].fa==-10)
		{
			node[w].fa=root;
			node[root].child.PB(w);
			make_tree(w);
			flag=false;
		}
	}
	if(flag==true) node[root].isdi=0;//叶子结点
	else node[root].isdi=1;//非叶子结点
}

int get_f0(int root)
{
	int sum=0;
		vector <int> ::iterator pp;
	if(node[root].isdi==0) return INFI;
	else
	{
		for(pp=node[root].child.begin();pp!=node[root].child.end();pp++)
			sum+=get_f2(*pp);
//		f[root][0]=sum;
		return sum;
	}
}

int get_f1(int root)
{
	int sum=0;
		vector <int> ::iterator pp;
	if(node[root].isdi==0) return 0;
	else
	{
		for(pp=node[root].child.begin();pp!=node[root].child.end();pp++)
			sum+=get_f0(*pp);
//		f[root][0]=sum;
		return sum;
	}
}

int get_f2(int root)
{
	int sum=1;
		vector <int> ::iterator pp;
	if(node[root].isdi==0) return 1;
	else
	{
		for(pp=node[root].child.begin();pp!=node[root].child.end();pp++)
			sum+=getmin(get_f2(*pp),get_f1(*pp));
//		f[root][0]=sum;
		return sum;
	}
}
void arc_node(int num)
{//num是点数
	int i,root;
	for(i=1;i<=num-1;i++)
	{
		arc[i+num-1].first=arc[i].second;
		arc[i+num-1].second=arc[i].first;
	}
	sort(arc+1,arc+2*num-1,cmp);
	node[arc[1].first].from=1;
	for(i=2;i<=2*num-2;i++)
	{
		if(arc[i].first!=arc[i-1].first)
		{
			node[arc[i-1].first].to=i-1;
			node[arc[i].first].from=i;
		}
	}
	node[arc[2*num-2].first].to=2*num-2;
	for(i=1;i<=num;i++) {node[i].fa=-10;node[i].isdi=-10;node[i].child.clear();}
	root=1;
	node[root].fa=-1;
	make_tree(root);
//	print_tree(num);
}	

void solve(int num)
{
	int ans,root;
	arc_node(num);
	root=1;
	ans=getmin(get_f2(root),get_f0(root));
//	print_f(num);
	printf("%d\n",ans);
}

int main()
{
	int i,num,begin=0;
	while(begin==0)
	{
		scanf("%d\n",&num);
		for(i=1;i<=num-1;i++)
			scanf("%d %d",&arc[i].first,&arc[i].second);
		solve(num);
		scanf("%d\n",&begin);
	}
	return 0;
}