2508227_ce.cc

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <vector>
#include <algorithm>
#define Max(a,b) a>b?a:b
using namespace std;

int n;
vector <int> tree[201];
vector <int> flor[201];
char str[201][101];
int no, max;

int get_id(char s[])
{
	int i;

	for(i = 0; i < no; i++)
		if(strcmp(str[i],s)==0)
			return i;
	strcpy(str[no],s);
	return no++;
}

void dfs(int v,int b)
{
	int i;

	flor[b].push_back(v);
	if(b>max)
		max = b;
	for(i = 0; i < tree[v].size(); i++)
		dfs(tree[v][i],b+1);
}

int main()
{
	int i, j;
	char l[101], r[101];
	int num[201][2], uni[201][2];

	while(scanf("%d",&n),n)
	{
		for(i = 0; i < n; i++)
			tree[i].clear(),flor[i].clear();
		no = 0;
		cin>>l;
		get_id(l);
		for(i = 1; i < n; i++)
		{
			cin>>l>>r;
			tree[get_id(r)].push_back(get_id(l));
		}
		max = -1;
		dfs(0,0);
		memset(num,0,sizeof(num));
		memset(uni,0,sizeof(uni));
		for(i = max; i >= 0; i--)
		{
			for(j = 0; j < flor[i].size(); j++)
				if(!tree[flor[i][j]].size())
				{
					num[flor[i][j]][0] = 1;
					num[flor[i][j]][1] = 0;
					uni[flor[i][j]][0] = uni[flor[i][j]][1] = 0;
				}
				else
				{
					int v1, v0;

					v0 = 1;v1 = 0;
					for(int k = 0; k < tree[flor[i][j]].size(); k++)
					{
						int ri = flor[i][j];
						v0 += num[tree[flor[i][j]][k]][1];
						uni[flor[i][j]][0] |= uni[tree[flor[i][j]][k]][1];
						v1 += Max(num[tree[flor[i][j]][k]][1],num[tree[flor[i][j]][k]][0]);
						if(num[tree[flor[i][j]][k]][1]>num[tree[flor[i][j]][k]][0])
							uni[flor[i][j]][1] |= uni[tree[flor[i][j]][k]][1];
						else
							if(num[tree[flor[i][j]][k]][1]<num[tree[flor[i][j]][k]][0])
								uni[flor[i][j]][1] |= uni[tree[flor[i][j]][k]][0];
							else
								uni[flor[i][j]][1] = 1;
					}
					num[flor[i][j]][0] = v0;
					num[flor[i][j]][1] = v1;
				}
		}
		max = Max(num[0][0],num[0][1]);
		printf("%d ",max);
		if(num[0][0]==num[0][1])
			printf("No");
		else
		{
			if(num[0][0]>num[0][1])
			{
				if(uni[0][0])
					printf("No");
				else
					printf("Yes");
			}
			else
			{
				if(uni[0][1])
					printf("No");
				else
					printf("Yes");
			}
		}
		printf("\n");
	}
	return 1;
}