1848.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream>
#include <vector>
using namespace std;
const int max = 999999;
bool e[100][100];
int ans[100] ,n;
vector<int> son[100];
int father[100];
int has[100][100];
int num[100];
void search(int a,int f)
{
	int i,j;
	num[a]=1;
	has[a][0]=a;
	father[a]=f;
	son[a].clear();
	for(i=0;i<n;i++)
	if(e[a][i]&&i!=f)
	{
		son[a].push_back(i);
		search(i,a);

		for(j=0;j<num[i];j++)
			has[a][num[a]++]=has[i][j];
	}
}
void init()
{
	int i,j,k;
	cin>>n;	
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		e[i][j]=0;
	for(i=0;i<n-1;i++)
	{
		cin>>j>>k;
		e[j-1][k-1]=e[k-1][j-1]=1;
	}
	search( 0, -1);
	for(i=0;i<n;i++)
			ans[i]=max;
}
int get_son(int r,int k)
{
	int i,temp=0;
	for(i=0;i<son[r].size();i++)
	if(son[r][i]!=k)
		temp+=ans[son[r][i]];	
	return temp;
}
void count(int r)
{
	int m,i,j,k,temp,a,b,s,h[100];
	h[0]=r;m=1;
	for(i=0;i<son[r].size();i++)
		count(son[r][i]);
	for(i=0;i<son[r].size();i++)
	{
		s=son[r][i];
		for(j=1;j<m;j++)
		for(k=0;k<num[s];k++)
		{
			a=h[j];	b=has[s][k];
			temp=get_son(a,-1)+get_son(b,-1);			
			while(temp<max&&father[a]!=r)
			{
				temp+=get_son(father[a],a);
				a=father[a];
			}
			while(temp<max&&father[b]!=r)
			{
				temp+=get_son(father[b],b);
				b=father[b];
			}
			if(temp<max)
				temp+=get_son(r,-1)-ans[a]-ans[b];

			if(temp+1<ans[r])ans[r]=temp+1;
		}
		for(k=1;k<num[s];k++)
		{
			b=has[s][k];
			temp=get_son(b,-1);
			while(temp<max&&father[b]!=r)
			{
				temp+=get_son(father[b],b);
				b=father[b];
			}	
			if(temp<max)temp+=get_son(r,b);
			if(temp+1<ans[r])ans[r]=temp+1;
		}		
		for(j=0;j<num[s];j++)
			h[m++]=has[s][j];
	}

}
int main()
{
	init();
	count(0);

	if(n<3||ans[0]>=max)cout<<-1<<endl;
	else cout<<ans[0]<<endl;

	return 0;
}