party at hali-bula(天津)~.cpp

来自「湖南大学ACM-OJ的部分题目代码」· C++ 代码 · 共 134 行

#include <iostream>
#include <cstring>
using namespace std;
 
struct Node{
	char name[128];
	int cnt;
	int son[256];
};
Node node[256];
 
int d[256][2], s[256][2], n;
 
int dp(int i, bool flag)
{
	if (d[i][flag] != -1)
		return d[i][flag];
	
	if (flag == 0)
	{
		int sum = 0;
		for (int j = 0; j < node[i].cnt; j++)
		{
			if (dp(node[i].son[j], 0) == dp(node[i].son[j], 1))
			{
				s[i][0] = 1;
				sum += dp(node[i].son[j], 0);
			}
			else if (dp(node[i].son[j], 0) > dp(node[i].son[j], 1))
			{
				sum += dp(node[i].son[j], 0);
				if (s[node[i].son[j]][0] == 1)
					s[i][0] = 1;
			}
			else
			{
				sum += dp(node[i].son[j], 1);
				if (s[node[i].son[j]][1] == 1)
					s[i][0] = 1;
			}
		}
		d[i][0] = sum;
	}
	else
	{
		d[i][1] = 1;
		for (int j = 0; j < node[i].cnt; j++)
		{
			d[i][1] += dp(node[i].son[j], 0);
			if (s[node[i].son[j]][0] == 1)
				s[i][1] = 1;
		}
	}
	
	return d[i][flag];
}
 
int main()
{
	int i, j;
	char name1[128], name2[128];
	
	while (scanf("%d", &n) && n)
	{
		int node_num = 0;
		getchar();
		gets(name1);
		node[node_num].cnt = 0;
		strcpy(node[node_num++].name, name1);
		
		for (i = 1; i < n; i++)
		{
			scanf("%s %s", name1, name2);
			getchar();
			
			int u;
			for (j = 0; j < node_num; j++)
			{
				if (strcmp(name1, node[j].name) == 0)
				{
					u = j;
					break;
				}
			}
			if (j == node_num)
			{
				node[node_num].cnt = 0;
				strcpy(node[node_num++].name, name1);
				u = node_num - 1;
			}
			
			for (j = 0; j < node_num; j++)
			{
				if (strcmp(name2, node[j].name) == 0)
				{
					node[j].son[node[j].cnt++] = u;
					break;
				}
			}
			
			if (j == node_num)
			{
				node[node_num].cnt = 0;
				strcpy(node[node_num++].name, name2);
				node[node_num-1].son[node[node_num-1].cnt++] = u;
			}
		}
		
		memset(d, -1, sizeof(d));
		memset(s, 0, sizeof(s));
	
		int a = dp(0, 0);
		int b = dp(0, 1);
		if (a == b)
			printf("%d No\n", a);
		else if (a > b)
		{
			printf("%d ", a);
			if (s[0][0] == 1)
				printf("No\n");
			else 
				printf("Yes\n");
		}
		else
		{
			printf("%d ", b);
			if (s[0][1] == 1)
				printf("No\n");
			else
				printf("Yes\n");
		}
	}
	return 0;
}