出处http://lishun618-163-com.iteye.com/blog/1489567
#include<iostream>
using namespace std;
typedef struct Node1{
int index;
Node1* next;
}Child;
typedef struct Node{
int parent;
int child_num;
int live_child;
Node1* child;
}Element;
int stone_num = 0;
int free_stone = 0;
int BFSGetNodeWithMaxChild(int root,Element T[],int n);
void placeStone(int index,Element T[],int n);
int main()
{
int tree_num;
cin >> tree_num;
for(int i = 0; i < tree_num; i++)
{
stone_num = 0;
free_stone = 0;
int tree_nodes;
cin >> tree_nodes;
Element * T = new Element[tree_nodes+1];
for(int j = 0; j <= tree_nodes; j++)
{
T[j].parent = 0;
T[j].child_num = 0;
T[j].child = NULL;
}
for(int j = 0; j < tree_nodes; j++)
{
int node_k, child_num;
cin >> node_k >> child_num;
T[node_k].child_num = child_num;
T[node_k].live_child = child_num;
for(int k = 0; k < child_num; k++)
{
Child * new_child = new Child;
cin >> new_child->index;
T[new_child->index].parent = node_k;
new_child->next = T[node_k].child;
T[node_k].child = new_child;
}
}
Child * guard = new Child;
guard->index = 1;
guard->next = NULL;
T[0].child = guard;
T[0].live_child = 1;
T[0].child_num = 1;
int key = BFSGetNodeWithMaxChild( 1, T,tree_nodes);
placeStone(key,T,tree_nodes);
cout << stone_num << endl;
for(int k = 0; k <= tree_nodes; k++)
{
if(T[k].child == NULL) continue;
Child* p = T[k].child;
Child * next;
do{
next = p->next;
delete p;
p = next;
}while(next != NULL);
}
delete[]T;
}
}
int BFSGetNodeWithMaxChild(int root,Element T[],int n)
{
int queue[n];
int head = 0,tail = 0;
int key = root;
queue[tail++] = root;
int temp;
while(tail != head)
{
temp = queue[head];
head = (head + 1) % n;
if(T[key].live_child <= T[temp].live_child)
key = temp;
Child * p = T[temp].child;
while(p != NULL)
{
queue[tail] = p->index;
tail = (tail + 1) % n;
p = p->next;
}
}
return key;
}
void placeStone(int index,Element T[],int n)
{
if(index == 0)
return;
int parent = T[index].parent;
Child * p = T[parent].child;
if(p->index == index)
{
T[parent].child = p->next;
delete p;
}else{
while(p->next != NULL)
{
if(p->next->index == index){
p->next = p->next->next;
break;
}
p = p->next;
}
}
T[parent].live_child--;
if(free_stone < T[index].live_child)
{
int more = T[index].live_child - free_stone;
stone_num += more;
free_stone += more - 1;
}
if(T[parent].live_child == 0)
{
free_stone += T[parent].child_num - 1;
placeStone(parent, T,n);
}else{
int new_root = BFSGetNodeWithMaxChild(parent,T, n);
placeStone(new_root,T,n);
}
}
分享到:
相关推荐
1、数据来源:北京大学数字金融中心 2、时间跨度:2011-2020年 3、区域范围:全国 4、指标说明: 其中县级数据从2014年开始,北大数字普惠金融研究院在2014年的时候只计算了1754个县的数据,所以拿到资料的小伙伴...
2021年3月最新北大中心核心目录,中文核心期刊要目总览(2021年版)(北京大学图书馆).pdf
高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学高等代数\+北京大学...
北京大学数字普惠金融指数
2019年北京大学寒假学堂测试(面向高中学生)数学试卷及答案(20211021012105).pdf
北大POJ1027-The Same Game 解题报告+AC代码
北大考博辅导:北京大学环境科学与工程(环境健康)考博难度解析及经验分享.pdf北大考博辅导:北京大学环境科学与工程(环境健康)考博难度解析及经验分享.pdf北大考博辅导:北京大学环境科学与工程(环境健康)考博难度...
高等代数课本北大版高等代数课高等代数课本北大版本北大版
北京大学-概率论与数理统计练习题(公共)答案大合集.pdf
北京大学的PPT,主要提供给大家一种制作PPT的模板,学习一下人家是怎么使用的PPT软件。
北京大学 地理信息系统概论专业课 真题 两年,但是不知道具体时间。
北京大学《高等代数I》期中试卷(含答案)
html结课作业,仿北京大学官网,需要实验报告的点这:https://download.csdn.net/download/weixin_44771551/12524589
北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案北京大学高等代数答案
ACM题解 训练指南 北大ACM题解 北大ACM训练指南 北大ACM题解训练指南 北京大学ACM题目 源代码 POJ源代码 POJ做指南
《概率论与数理统计》——————北京大学出版社 21世纪全国高校应用人才培养基础课规划教材
PCB板缺陷检测数据集(北京大学693数据增强,6930)
北京大学《高等数学》大一上期末复习资料
2021年北京大学优秀中学生寒假学堂测试数学试题详细解析(完整版).pdf
北京大学2006年电子线路(模电部分)考研试题与答案 北京大学2006年电子线路(模电部分)考研试题与答案