北大 1694 An Old Stone Game

出处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);
	}
	
}