(利用树的遍历求解层次性问题8.4.10)POJ 1634 Who's the boss?(求解某一个节点的父亲以及他的孩子的数目)

/* 
 * POJ_1634_1.cpp 
 * 
 *  Created on: 2013年11月6日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
#include <cstdio>  
#include <vector>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 30010;  
int m, q;  
  
struct Node {//员工节点  
    int id;  
    int salary;  
    int height;  
    int father;  
    int sons;  
    vector<int> vec;  
  
    bool operator<(const Node& t) const {  
        return salary < t.salary;  
    }  
} node[maxn];  
  
void init() {  
    int i, j;  
    for (i = 1; i <= m; ++i) {//初始化每一个员工的信息  
        scanf("%d%d%d", &node[i].id, &node[i].salary, &node[i].height);  
        node[i].father = 0;  
        node[i].sons = 0;  
        node[i].vec.clear();  
    }  
  
    sort(node + 1, node + 1 + m);//将每一个员工按照工资的高地进行排序  
  
    for (i = 1; i <= m; ++i) {//便利每一个员工,找到身高比他高的第一个人,并将其这位该员工的父亲  
        j = i + 1;  
        while (node[j].height < node[i].height && j <= m) {  
            ++j;  
        }  
  
        if (j <= m) {  
            node[i].father = node[j].id;  
            node[j].vec.push_back(i);  
            node[j].sons++;  
        }  
    }  
  
    for(i = 1 ; i <= m ;++i){//计算每一个员工的孩子数  
        for(j = 0 ; j < node[i].vec.size() ; ++j){  
            node[i].sons += node[node[i].vec[j]].sons;  
        }  
    }  
  
}  
  
void gao(int id){//用于输出每一个员工的父亲的编号和孩子数  
    int i;  
    for(i = 1 ; i <= m ; ++i){  
        if(node[i].id == id){  
            printf("%d %d\n",node[i].father,node[i].sons);  
            return ;  
        }  
    }  
}  
  
  
int main(){  
    int t;  
    scanf("%d",&t);  
    while(t--){  
        scanf("%d%d",&m,&q);  
  
        init();  
  
        while(q--){  
            int id;  
            scanf("%d",&id);  
            gao(id);  
        }  
    }  
  
    return 0;  
}  

补充：软件开发 , C++ ,

上一个：C++ operator new placement new
下一个：C++ 友元函数 友元类