poj 2021

 

题意：Ted今年100岁，给出n对他家族的关系：“父亲名，孩子名，生孩子时父亲年龄”，求出家族所有人现在的岁数。

思路：基础题，可以用bfs做。要注意排序输出时，当年龄相同，要按姓名的字典顺序输出。

代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int Max = 105;

struct data
{
    int age;
    char name[20];
}node[Max];

bool cmp(data &a, data &b)
{
    if(a.age > b.age) 
		return true;
    if(a.age == b.age && strcmp(a.name, b.name) < 0) 
		return true;   //  字典序排序。 
    return false;
}

int main()
{
    char fa[Max][20], ch[Max][20];
    int textCase, t, n, k, i, j, year[Max];
    cin >> textCase;
    node[0].age = 100;
    strcpy(node[0].name, "Ted");
    for(t = 1; t <= textCase; t++)
	{
        cin >> n;
        for(i = 1; i <= n; i ++)
            cin >> fa[i] >> ch[i] >> year[i];
        for(i = 0, k = 1; i < n; i ++)
            for(j = 1; j <= n; j ++)
                if(strcmp(node[i].name, fa[j]) == 0)
				{
                    node[k].age = node[i].age - year[j];
                    strcpy(node[k].name, ch[j]);
                    k ++;
                }
				sort(node, node+n+1, cmp);
				cout << "DATASET " << t << endl;
				for(i = 1; i <= n; i ++)
					cout << node[i].name << ' ' << node[i].age << endl;
    }
    return 0;
}