Stewart教授是一家公司总裁的顾问，这家公司计划一个公司聚会。这个公司有一个层次式的结构；也就是说，管理关系形成一棵以总裁为根的树。人事部给每个雇员以喜欢聚会的程度来排名，这是个实数。为了使每个参加者都喜欢这个聚会，总裁不希望一个雇员和他（她）的直接上司同时参加。
Stewart教授面对一棵描述公司结构的树，使用了左子女、右兄弟表示法。树中每个结点除了包含指针，还包含雇员的名字和该雇员喜欢聚会的排名。描述一个算法，它生成一张客人列表，使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。
分析：求出以每个节点为根节点的子树去或者不去的最大喜欢程度和，以此往上推，本题就是求根节点去或者不去的最大喜欢程度。显然，这具有最优子序列结构。给每个节点增加两个域，select,unsel,select[i]表示i节点去时，以i节点为根的子树的喜欢程度和，unsel[i]表示i节点不去时，所获得的喜欢程度和。
公式如下：
r.select=r.data+sum(unsel[j]);//j为r的孩子，r.data为节点r的喜欢程度
r.unsel=sum(max{unsel[j],select[j]});当i选择去时，它的孩子节点肯定不能去；当i不去时，其孩子节点可以选择去或者不去；然后根据求出的根节点的最大喜欢程度和，找出参加的名单。首先是计算每个节点为根的子树的最大喜欢程度和。
// gongsujuhui.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
typedef struct TreeNode *Position;
typedef struct TreeNode *Tree;
struct TreeNode {
int love;//喜欢聚会的程度
Position parent, leftChild, rsibling;
int select, unselect; //去或不去以该节点为根的子树的喜欢程度
bool go;
};
Tree initTree(int love[],int n) //初始化公司树，15个节点的二叉树,n是人数，love是喜欢程度
{
Tree T = (Tree)malloc(sizeof(TreeNode));
T->love = love[1];
T->parent = NULL;
T->rsibling = NULL;
T->go = true;
T->select = 0;
T->unselect = 0;
queue<Position> que;
que.push(T);
for (int i = 2; i <= n; i+=2)
{
Position pLeft = (Position)malloc(sizeof(TreeNode));
Position pRight = (Position)malloc(sizeof(TreeNode));
que.front()->leftChild = pLeft;
pLeft->love = love[i];
pRight->love = love[i + 1];
pLeft->parent = pRight->parent=que.front();
que.pop();
pLeft->rsibling = pRight;
pLeft->leftChild = NULL;
pRight->leftChild = NULL;
pRight->rsibling = NULL;
pLeft->go = pRight->go = true;
pLeft->select = pLeft->unselect = pRight->select = pRight->unselect = 0;
que.push(pLeft);
que.push(pRight);
}
return T;
}
void print(Tree T) //打印公司树
{
Position left, right;
queue<Position> que;
que.push(T);
while (!que.empty())
{
if(que.front()->go)cout << que.front()->love<<' ';
left = que.front()->leftChild;
que.pop();
if (left != NULL)
{
right = left->rsibling;
que.push(left);
if (right != NULL)
{
que.push(right);
}
}
}
cout << endl;
}
int sumUnselectSon(Position p)
{
Position left = p->leftChild;
int sum = left->unselect;
while (left->rsibling!=NULL)
{
left = left->rsibling;
sum += left->unselect;
}
return sum;
}
int sumMaxson(Position p)
{
Position left = p->leftChild;
int sum = left->select > left->unselect ? left->select : left->unselect;
while (left->rsibling != NULL)
{
left = left->rsibling;
sum += left->select > left->unselect ? left->select : left->unselect;
}
return sum;
}
void peopleSelect(Tree T)
{
stack<Position> sta;
Position p ;
p = T;
while (!sta.empty()||p!=NULL)
{
if(p!=NULL)
{
sta.push(p);
while (p->leftChild!=NULL)
{
p = p->leftChild;
sta.push(p);
}
}
p=sta.top();
sta.pop();
if (p->leftChild == NULL)
{
p->select = p->love;
p->unselect = 0;
}
else
{
p->select = p->love + sumUnselectSon(p);
p->unselect = sumMaxson(p);
}
p = p->rsibling;
}
}
void PeopleList(Tree T)
{
Position r, s;
r = T;
if (r == NULL) return;
else if (r->parent == NULL) {
if (r->select > r->unselect)
r->go = 1;
else
r->go = 0;
}
else
{
if (r->parent->go)
r->go = false;
else {
if(r->select > r->unselect)
r->go = 1;
else
r->go = 0;
}
}
if (r->leftChild)
{
r = r->leftChild;
s = r->rsibling;
PeopleList(r);
PeopleList(s);
}
}
int main()
{
int love[] = { 0,2,5,3,4,8,6,7,17,9,10,16,12,8,3,15 };
Tree T = initTree(love, 15);
print(T);
peopleSelect(T);
PeopleList(T);
print(T);
while (1);
return 0;
}