首页 > 其他 > 详细

POJ 2021 Relative Relatives(map+树的遍历)

时间:2014-01-18 18:38:36      阅读:406      评论:0      收藏:0      [点我收藏+]

题意:
  今天是Ted的100岁生日。凑巧的是,他家族里面每个人都跟他同一天生日,但是年份不同。
  现在只给出一些 父亲的名字,孩子的名字,以及孩子出生时父亲的年龄,
  要求将Ted以外的家族成员按年龄降序排序,如果年龄相同,则按字母排序。

思路:遍历树。
  根据题意,可通过父子关系建立一个有权无向树,Ted作为树的根节点。通过从Ted所在节点开始遍历树,给每个节点赋值。
  最后根据每个成员的年龄排序即可。
  这里用到map,建立名字到编号的映射,从而获取一个人在树中的节点编号。

 

bubuko.com,布布扣
#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;
}
bubuko.com,布布扣

POJ 2021 Relative Relatives(map+树的遍历)

原文:http://www.cnblogs.com/chenxiwenruo/p/3525044.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!