2506746_wa.cpp

北大大牛代码 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];

	freopen("D.in","r",stdin);
	freopen("res.txt","w",stdout);
	while(scanf("%d",&n),n)
	{
		for(i = 0; i < n; i++)
			tree[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);
		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;
				}
				else
				{
					int v1, v0;

					v0 = 1;v1 = 0;
					for(int k = 0; k < tree[flor[i][j]].size(); k++)
					{
						v0 += num[tree[flor[i][j]][k]][1];
						v1 += Max(num[tree[flor[i][j]][k]][1],num[tree[flor[i][j]][k]][0]);
					}
					num[flor[i][j]][0] = v0;
					num[flor[i][j]][1] = v1;
				}
		}
		max = Max(num[0][0],num[0][1]);
		printf("%d ",max);
		int queue[201];
		int f, r;

		f = r = -1;
		queue[++f] = 0;
		while(f!=r)
		{
			r++;
			for(i = 0; i < tree[queue[r]].size(); i++)
			{
				for(j = 0; j < 2; j++)
					if(num[tree[queue[r]][i]][j]==max)
					{
						printf("No\n");
						goto con;
					}
				queue[++f] = tree[queue[r]][i];
			}
		}
		printf("Yes\n");
con:
		;
		
	}
	return 1;
}