substr.cpp

给定1 棵有n 个结点的树T。子树分割问题要求从树T 中删除尽可能少的边得到一个恰有k 个结点的连通分支。

#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");

void Maketree(int **a,int n)
{
	int x,y,i;
	for(i=1;i<n;i++)
	{
		fin>>x>>y;
		a[x][1]=1;
		a[x][y]=1;
	}
}
void Size(int **a,int n,int *son)
{
	int i,j;
	for(i=n;i>=1;i--)
		for(j=2;j<=n;j++)
			if(a[i][j])
				son[i]+=son[j];
}
void Swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
int Partition(int a[],int p,int r)
{
	int i=p,j=r+1;
	int x=a[p];
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j) break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void Quicksort(int a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		Quicksort(a,p,q-1);
		Quicksort(a,q+1,r);
	}
}

void main()
{
	if(fin.fail())
	{
		cout<<"The input.txt is not exist!"<<endl;
		exit(1);
	}
	int **a,n,k,i,j;
	fin>>n>>k;
	a=new int *[n+1];
	for(i=0;i<=n;i++)
		a[i]=new int [n+1];
	for(i=0;i<=n;i++)
		for(j=0;j<=n;j++)
			a[i][j]=0;
	Maketree(a,n);
	int *son=new int [n+1];
	for(i=0;i<=n;i++)
		son[i]=1;
	Size(a,n,son);
	Quicksort(son,0,n);
	int step=0,sub=n-k;
	for(i=n;sub>0;i--)
		if(son[i]<=sub)
		{
			sub=sub-son[i];
			step++;
		}
	fout<<step;
}