d 森林问题.cpp

设T 是一棵带权树

#include <fstream.h>

void main()
{
	//读数
	ifstream inf("input.txt");
	ofstream outf("output.txt");
	long number=0,i=0,j=0;
	inf>>number;
	struct node
	{
		long childnum;
		long fnode;
		double weight;
	};
	struct node *treenode=new node[number+1];
	//建立父亲数组
	long temp;
	treenode[1].fnode=0;
	treenode[1].weight=0;
    for (i=1;i<=number;i++)
	{
		inf>>treenode[i].childnum;
		for (j=1;j<=treenode[i].childnum;j++)
		{
			inf>>temp;
			treenode[temp].fnode=i;
			inf>>treenode[temp].weight;
		}
	}
	double d=0;
	inf>>d;
	if (d<0)
		outf<<"No Solution!"<<endl;
	else
	{
		double *w=new double[number+1];
		for (i=0;i<=number;i++)
			w[i]=0;
		long count=0;
		double tWeight;
		for (i=number;i>0;i--)
		{
			if (w[i]>d)
			{
				count++;
				treenode[i].weight=0;
				w[i]=0;
			}
			if (treenode[i].childnum==0)
			{
				treenode[treenode[i].fnode].childnum--;
				//计算各结点的最大路长
				tWeight=treenode[i].weight+w[i];
				w[treenode[i].fnode]=(tWeight>w[treenode[i].fnode])?tWeight:w[treenode[i].fnode];
			}
		}
		outf<<count;
		delete []w;
		delete []treenode;
	}
}