公司里的那点事儿
描述
对于一间公司来说，它成立之时所做的第一件事恐怕就是任命CEO了。之后，CEO就会开始雇用员工，也会有员工离职去别的公司。假设公司中的每一个员工（包括 CEO在内）都可以直接雇用新的员工，而公司中的所有员工（包括CEO）也都可能会跳槽离开，则某公司在成立一段时间之后的的组织结构如图1：
VonNeumann是公司的CEO，他直接雇用了两个人，分别是Tanenbaum和Dijkstra。在公司中，某员工的几个直接下属，他们的职位是由员工们的工龄决定的，在图中即表现为从从左至右职位越来越低，譬如Tanenbaum的职位就比Dijkstra要高。
当一个员工雇用了新的下属时，该下属在该员工雇佣的所有下属中，职位是最低的。假设VonNeumann又雇用了Shannon，则VonNeumann的三名下属职位从高到低分别是Tanenbaum、Dijkstra和Shannon。
当公司中的员工离职，则有两种情况。若他没有雇用任何下属，则他会被从公司的组织结构中拿掉。若他有直接的下属，则他的直接下属中职位较高的人，会升职并补上缺位。而该下属若也有下属，则他的下属中职位最高的，会补上他升值后空出的位子。以此类推，直到某个尚未雇用下属的员工升职。
假设图1中的Tanenbaum跳槽离开了，则Stallings会补上它的位置，而Knuth会补上Stallings的位置。图2图3分别展示了基于图1的两种的操作的结果。图2： VonNeumann雇用了Shannon。图3： Tanenbaum跳槽。
输入
输入的第一行是 CEO 的姓名。题目中所有的人名的长度都在2-20之间，且由大小写字母、数字和短线（减号）组成。每个名字都包含至少一个大写和一个小写字母。
在第一行后会有很多行内容，他们由如下的规则构成：
- [老员工] hires [新员工]
- fire [老员工]
[老员工] 是已经在公司工作的人的名字，而[新员工]是即将被雇用的员工的名字。以上三种规则组成的内容可能会按照任何顺序出现。但公司中会至少有一名员工（CEO），且公司的规模最大不会超过 1000 人。
输出
对于每一个打印命令，按照如下规则输出当前公司的结构信息：
- 每一行包含一个人名
- 第一行是CEO的名字，从第一列开始
- 对于图4形式的树
- 输出如下
VonNeumann +Tanenbaum ++Stallings +++Knuth +++Hamming +++Huffman ++Silberschatz +Dijkstra
- *关于print的说明：从ceo开始打印，职位每降低一个等级（参考图片和输出），在名字前面加上一个加号。先序（自己->左枝->右枝）输出整棵树的节点。整棵树遍历完之后输出一行"---------"(具体长度看测试用例1)。
- 输入以EOF结束
| 测试输入 |
期待的输出 |
时间限制 |
内存限制 |
额外进程 |
|
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
|
以文本方式显示
|
1秒 | 64M | 0 |
题意：略过。
题解：刚看到这题实在不懂这跟博弈搜索练习有什么关系，看了POJ2003的题解感觉这纯粹是在考对数据结构的掌握，尤其是对C++的STL里的一些容器的使用。（后来学长讲蒙特卡洛和UCT时说这个是练习我们建招法树用的，这道题中使用的方法可以将多叉树转为二叉树，想想确实很有道理，也很佩服当初是哪位学长找的这题用来训练招法树建立的。）
参考博客：POJ 2003 Hire and Fire (多重链表 树结构 好题)
map,list用的很强，map提供了一种对应关系容器，list提供了链表结构，这比自己写要舒坦多了。
#include<string>
#include<list>
#include<map>
#include<iostream>
using namespace std;struct Tree
{Tree*father;//与父节点相连string name;//本节点的员工名字list<Tree*>sons;//本节点员工的下属
};map<string, Tree*>StrMap;//建立员工名字与其树节点的对应关系，方便后来的查找操作
Tree *CompanyLink;void Print(Tree*cur_node, int range)//打印输出
{if (!cur_node)//说明没有下属了return;for (int i = 0; i<range; i++)printf("+");cout << cur_node->name << endl;list<Tree*>::iterator iter = cur_node->sons.begin();//迭代器iteratorfor (; iter != cur_node->sons.end(); ++iter)//在这里++iter比iter++效率高，详见C++ iterator 前++ 后++ 效率区别Print(*iter, range + 1);
}
int main()
{CompanyLink = new Tree();//开辟内存空间string EmployName, StaffName, op;//上司，下属，处理hires的cin >> EmployName; StrMap[EmployName] = CompanyLink;CompanyLink->name = EmployName;while (cin >> EmployName){if (EmployName != "print"){if (EmployName != "fire")//hires部分应该还是比较好理解的，用指针操作可以直接改值，不然不能改值{cin >> op >> StaffName;Tree*cur_node = StrMap[EmployName];Tree*new_node = new Tree();new_node->name = StaffName;new_node->father = cur_node;cur_node->sons.push_back(new_node);StrMap[StaffName] = new_node;}else{cin >> StaffName;Tree*cur_node = StrMap[StaffName];StrMap.erase(StaffName);while (cur_node->sons.size() != 0)//一个员工晋级了，则他的第一个下属会顶替他的位置，不断重复至没有下属{cur_node->name = cur_node->sons.front()->name;//当前员工的名字被其第一个下属的名字覆盖，使用覆盖操作的好处在于不会改变原有职位的职工从属关系StrMap.erase(cur_node->name);//删去原有的对应关系StrMap[cur_node->name] = cur_node;//更新新的对应关系cur_node = cur_node->sons.front();//当前指针移动到其第一个下属位置}cur_node->father->sons.remove(cur_node);//没有下属了，则要删除list中的当前节点，因为和前一个重复了delete cur_node;//释放内存空间，之前只是切断了list中的链关系，并没有释放掉内存空间 cur_node = NULL;//指到0，防止出错}}else{Print(CompanyLink, 0);printf("------------------------------------------------------------\n");}}return 0;
}