题意：
今天是Ted的100岁生日。凑巧的是，他家族里面每个人都跟他同一天生日，但是年份不同。
现在只给出一些
父亲的名字，孩子的名字，以及孩子出生时父亲的年龄，
要求将Ted以外的家族成员按年龄降序排序，如果年龄相同，则按字母排序。
思路：遍历树。
根据题意，可通过父子关系建立一个有权无向树，Ted作为树的根节点。通过从Ted所在节点开始遍历树，给每个节点赋值。
最后根据每个成员的年龄排序即可。
这里用到map，建立名字到编号的映射，从而获取一个人在树中的节点编号。
#include <iostream> #include <stdio.h> #include <map> #include <string> #include <string.h> #include <vector> #include <algorithm> using namespace std; map<string,int> person; int n; //即题目中的X值 struct Line{ string fname; //父亲的名字 string cname; //孩子的名字 int fage; //孩子出生时，父亲的年龄 }line[105]; struct Node{ string name; //名字 int age; //年龄 int fage; //出生时父亲的年龄，则该节点的年龄=父亲的年龄-fage vector<int> son; //存储孩子的编号 bool operator<(const Node tmp)const{ if(age==tmp.age) return name<tmp.name; else return age>tmp.age; } }node[105]; //遍历，求节点的年龄 void dfs(int u){ for(int i=0;i<node[u].son.size();i++){ int v=node[u].son[i]; node[v].age=node[u].age-node[v].fage; dfs(v); } } int main() { int t; scanf("%d",&t); for(int q=1;q<=t;q++){ printf("DATASET %d\n",q); person.clear(); for(int i=1;i<105;i++) node[i].son.clear(); int idx=0; person["Ted"]=++idx; scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>line[i].fname>>line[i].cname>>line[i].fage; //如果不存在该字符串的映射，即映射为0，则建立映射关系 if(!person[line[i].fname]) person[line[i].fname]=++idx; if(!person[line[i].cname]){ person[line[i].cname]=++idx; } } //根节点 node[1].name="Ted"; node[1].age=100; int u,v; for(int i=1;i<=n;i++){ u=person[line[i].fname]; v=person[line[i].cname]; node[u].name=line[i].fname; node[u].son.push_back(v); node[v].name=line[i].cname; node[v].fage=line[i].fage; } dfs(1); sort(node+1,node+idx+1); for(int i=1;i<=idx;i++){ if(node[i].name!="Ted") cout<<node[i].name<<" "<<node[i].age<<endl; } } return 0; }