POJ 2003 Hire and Fire (多重链表 树结构 好题)

 

Hire and Fire
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 2316   Accepted: 655

 

Description

In this problem, you are asked to keep track of the hierarchical structure of an organization's changing staff. As the first event in the life of an organization, the Chief Executive Officer (CEO) is named. Subsequently, any number of hires and fires can occur. Any member of the organization (including the CEO) can hire any number of direct subordinates, and any member of the organization (including the CEO) can be fired. The organization's hierarchical structure can be represented by a tree. Consider the example shown by Figure 1:
POJ 2003 Hire and Fire (多重链表 树结构 好题)

VonNeumann is the CEO of this organization. VonNeumann has two direct subordinates: Tanenbaum and Dijkstra. Members of the organization who are direct subordinates of the same member are ranked by their respective seniority. In the diagram, the seniority of such members decrease from left to right. For example Tanenbaum has higher seniority than Dijkstra.

When a member hires a new direct subordinate, the newly hired subordinate has lower seniority than any other direct subordinates of the same member. For example, if VonNeumann (in Figure 1) hires Shannon, then VonNeumann's direct subordinates are Tanenbaum, Dijkstra, and Shannon in order of decreasing seniority.

When a member of the organization gets fired, there are two possible scenarios. If the victim (the person who gets fired) had no subordinates, then he/she will be simply dropped from the organization's hierarchy. If the victim had any subordinates, then his/her highest ranking (by seniority) direct subordinate will be promoted to fill the resulting vacancy. The promoted person will also inherit the victim's seniority. Now, if the promoted person also had some subordinates then his/her highest ranking direct subordinate will similarly be promoted, and the promotions will cascade down the hierarchy until a person having no subordinates has been promoted. In Figure 1, if Tanenbaum gets fired, then Stallings will be promoted to Tanenbaum's position and seniority, and Knuth will be promoted to Stallings' previous position and seniority.

Figure 2 shows the hierarchy resulting from Figure 1 after (1) VonNeumann hires Shannon and (2) Tanenbaum gets fired:
POJ 2003 Hire and Fire (多重链表 树结构 好题)

Input

The first line of the input contains only the name of the person who is initially the CEO. All names in the input file consist of 2 to 20 characters, which may be upper or lower case letters, apostrophes, and hyphens. (In particular, no blank spaces.) Each name contains at least one upper case and at least one lower case letter.


The first line will be followed by one or more additional lines. The format of each of these lines will be determined by one of the following three rules of syntax:
[existing member] hires [new member]
fire [existing member]
print
Here [existing member] is the name of any individual who is already a member of the organization, [new member] is the name of an individual who is not a member of the organization as yet. The three types of lines (hires, fire, and print) can appear in any order, any number of times.

You may assume that at any time there is at least one member (who is the CEO) and no more than 1000 members in the organization.

Output

For each print command, print the current hierarchy of the organization, assuming all hires and fires since the beginning of the input have been processed as explained above. Tree diagrams (such as those in Figures 1 and 2) are translated into textual format according to the following rules:
Each line in the textual representation of the tree will contain exactly one name.
The first line will contain the CEO's name, starting in column 1.
The entire tree, or any sub-tree, having the form
POJ 2003 Hire and Fire (多重链表 树结构 好题)

will be represented in textual form as:
POJ 2003 Hire and Fire (多重链表 树结构 好题)

The output resulting from each print command in the input will be terminated by one line consisting of exactly 60 hyphens. There will not be any blank lines in the output.

Sample Input

VonNeumann
VonNeumann hires Tanenbaum
VonNeumann hires Dijkstra
Tanenbaum hires Stallings
Tanenbaum hires Silberschatz
Stallings hires Knuth
Stallings hires Hamming
Stallings hires Huffman
print
VonNeumann hires Shannon
fire Tanenbaum
print
fire Silberschatz
fire VonNeumann
print

Sample Output

VonNeumann
+Tanenbaum
++Stallings
+++Knuth
+++Hamming
+++Huffman
++Silberschatz
+Dijkstra

VonNeumann
+Stallings
++Knuth
+++Hamming
+++Huffman
++Silberschatz
+Dijkstra
+Shannon

Stallings
+Knuth
++Hamming
+++Huffman
+Dijkstra
+Shannon

Source

Rocky Mountain 2004

题目链接:http://poj.org/problem?id=2003

题目大意:看题面和输入输出很恐怖的样子,其实题意很简答,一棵树
A hires B 表示把B做为A的儿子
fire A 表示把A结点去掉,去掉以后其第一个儿子结点到它的位置,然后其第一个孙子结点到其第一个儿子结点出,以此类推。。。直到叶子
print 表示按先序遍历,遍历整棵树,+号个数表示当前点所在层的层数

题目分析:想到好的数据结构可以简化一大部分问题,像这种要对树上结点增删查的问题,我们采用多重链表来构树
多重链表结构体里有三个参数,点的名字,父指针,存储儿子指针的链表,还需要一个键值对存储作为子树根的结点对应的树指针,显然用map,具体操作看代码和注释吧

#include 
#include 
#include 
#include 
#include
using namespace std;

struct Tree
{
    string name;            //结点名字
    Tree *fa;               //结点父指针
    list  son;      //结点儿子指针链表
    Tree()
    {
        fa == NULL;
    }
};

map  mp;    //结点与其树指针的键值对

void Print(int dep, Tree *now)  //先序递归输出
{
    if(!now)
        return;
    for(int i = 0; i < dep; i++)
        printf(+);
    cout << now -> name << endl;
    for(list  :: iterator it = now -> son.begin(); it != now -> son.end(); it++)
        Print(dep + 1, *it);
    return;
}

void Fire(string del)   
{   
    Tree *s = mp[del];      //得到该点的树指针      
    while((int)s -> son.size() != 0)    //遍历最左位置
    {
        //下面三步相当于把当前结点的儿子上移
        s -> name = s -> son.front() -> name;  
        mp[s -> name] = s;
        s = s -> son.front();
    }
    //此时的s到达最左的叶子处,可以删除
    mp.erase(del);              //释放以del为根的子树
    s -> fa -> son.remove(s);   //将其从其父亲的儿子指针链表中删除
    delete s;                   //删除s
}

void Hire(string fir, string sec)
{
    Tree *f = mp[fir];          //得到父指针
    Tree *s = new Tree();       //新建一个指针域
    s -> fa = f;                //将其指向父指针
    s -> name = sec;            //命名
    mp[sec] = s;                //建立其与树指针的键值关系
    f -> son.push_back(s);      //将其加入父亲的儿子指针链表中
    return;
}

int main()
{
    string rt, fir, sec;
    cin >> rt;
    Tree *root = new Tree();
    mp[rt] = root;
    root -> name = rt;
    while(cin >> fir)
    {
        if(fir == print)
        {
            Print(0, root);
            printf(
);
        }
        else if(fir == fire)
        {
            cin >> sec;
            Fire(sec);
        }
        else
        {
            string tmp;
            cin >> tmp >> sec;
            Hire(fir, sec);
        }
    }
}


 

更多相关文章
  • 前言     一个成熟的大型网站(如淘宝.京东等)的系统架构并不是开始设计就具备完整的高性能.高可用.安全等特性,它总是随着用户量的增加,业务功能的扩展逐渐演变完善的,在这个过程中,开发模式.技术架构.设计思想也发生了很大的变化,就连技术人员也从几个人发展到一个部门甚至一条产品线.所以成熟的系统架构 ...
  • 前言 园子早早的就有人安装了VS 2015,自己也按捺不住了,也要赶快尝尝鲜!结果在其安装过程中一个小小的问题却困扰了我一天,这其中多亏了dudu耐心的解答才得以顺利完成,如果你也遇见这个问题,看过这篇文章后你就不会像我一样走太多的弯路[虽说耽误了时间但是也受益匪浅]! 话题 安装的过程以及详解就不 ...
  • httpd服务编译安装 httpd服务就是网页服务,不过Linux现在流行的httpd服务为apache服务. 我们这里编译安装的htppd服务也为apache服务. httpd服务的功能及作用应该不需要多做介绍了,我们直接进入正题,开始编译及安装. 首先需要先到官网下载httpd的编译安装包以及依 ...
  • 易网科技讯 8月11日消息,阿里巴巴(1688.HK)今日下午发布第二季度及半年度中期财报.财报数据显示,上半年总营业收入同比增长22%至人民币31.56亿元,净利润同比增加32%至人民币9.17亿元,现金及银行存款达人民币101亿元.第二季度营业收入为人民币16.23亿元,同比增长19%,净利润为 ...
  • 国内首个Ossim技术交流群(179084574),欢迎加入我们 参与51CTO[第242期]OSSIM,企业信息安全管理利器热门技术讨论 今天为大家介绍的OSSIM即开源安全信息管理系统是目前非常流行的开源安全架构体系.OSSIM通过将开源产品进行集成,从而提供一种能够实现安全监控功能的基础平台O ...
  • Windows8安装Oracle11.2.0.1                                         操作系统:Windows 8 企业版 64bit Oracle:11.2.0.1   64bit 1.Oracle下载地址 win 64位oracle 下载地址: htt ...
一周排行
  • 1.所需软件 apache_2.2.4-win32-x86-no_ssl,apache服务器 mod_jk-apache-2.2.4连接器,连接apache和tomcat apache-tomcat-6.0.33to ...
  • Pxe+kickstart制动安装系统 所需环境 pxe+kickstart+dhcp+tftp+(vsftp或www或nfs或nfs+vsftp) 由于本人在redhat6上环境中实验可能于rehat5有所不同,重 ...
  • 理解布局对于良好的Android程序设计非常重要.在这个教程里,你将学到相对布局的所有知识,相对布局用于将用户界面控件或小工具相对于其它控件或它们的父级布局组织在屏幕上.当使用正确的时候,相对布局可以是很强大和灵活布 ...
  • 10月以来,本市远程电信诈骗的发案率明显提高,据市公安局消息,目前110每天都能接到大量报案..咨询等各类涉及远程诈骗的电话.从即日起,北京警方开展为期一百天的打击防范电信诈骗专项行动,由民警负责值守重点地区银行的A ...
  • www.2cto.com:看起来通篇很简单,但是内涉的心理学啊,社工啊之类的其实是很复杂的. 局内人如果没有听说过这种诈骗,很容易被诱骗,所以这篇文章大家不妨分享下:   2011年11月29日,江苏省苏州市某投资公 ...
  • 作业题目: 作业- IT 行业博客网站分析和创新   同学们交上来的作业:   6个组作业的地址公布如下: 刘爽组这次把三个博客(CSDN,博客园,ITEYE)三个博客统一用同样的博客名称:amazingidiot ...
  • 多态 1 概念 面向对象系统的多态性是指不同的对象收到相同的的消息时, 执行不同的操作                编译时的多态性   多态性               运行时的多态性      编译时多态性主要 ...
  • 第一步,我们加上对html5的支持. <!--[if IE]> <script src="/public/html5.js" type="text/javascript ...
  • 1. oncontextmenu="window.event.returnValue=false" 将彻底屏蔽鼠标右键<table border oncontextmenu=return(f ...
  • 只想让自己安安静静在QQ音乐听歌,不希望朋友知道自己在听歌,如果不希望被别人打搅,下面的方法对你来说还是蛮有用的,有此需求的朋友可以参考下,希望对大家有所帮助 只想让自己安安静静在QQ音乐听歌,不希望朋友知道自己在听 ...