roads.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<assert.h>

FILE *inp,*outp;
struct point{int x;point *son,*bro;};
int num[200],x,y,i,n,p,head;
int g[200][200];
point *a[200],*p1,*p2,*Npo;
int Min(int t1,int t2){
	if (t1<t2) return t1;else
		       return t2;
}
int Max(int t1,int t2){
	if (t1>t2) return t1;else
		       return t2;
}
void Count(int head){
	if (head==0) return;
	int x;num[head]=1;
	if (a[head]->son!=NULL){
		x=a[head]->son->x;Count(x);num[head]+=num[x];
	};
	if (a[head]->bro!=NULL){
		x=a[head]->bro->x;Count(x);num[head]+=num[x];
	};
}
int King(int head,int p){
	if (head==0) return 0;
	if (g[head][p]!=-1) return g[head][p];
	g[head][p]=num[head]-p;
	int t1,t2,x1=a[head]->son->x,x2=a[head]->bro->x;
	point *p1;
	for (int i=Max(0,p-num[x2]);i<=Min(p,num[x1]+1);i++){
		if (i==0) t1=1;else
			      t1=King(x1,i-1);
		t2=King(x2,p-i);
        g[head][p]=Min(g[head][p],t1+t2);
	}
	return g[head][p];
}
main(){
	inp=fopen("roads.in","r");assert(inp);
	outp=fopen("roads.out","w");assert(outp);
	fscanf(inp,"%d%d",&n,&p);
	Npo=new point;Npo->x=0;num[0]=0;
	for (i=1;i<=n;i++){
		a[i]=new point;
		a[i]->x=i;a[i]->son=Npo;a[i]->bro=Npo;
	}
	memset(num,0,sizeof(num));
	for (i=1;i<n;i++){
	    fscanf(inp,"%d%d",&x,&y);num[y]=1;
		if (a[x]->son==Npo) a[x]->son=a[y];
		else{
			p2=a[x]->son;
			while (p2->bro!=Npo) 
				p2=p2->bro;
			p2->bro=a[y];
		};      
	}
	head=1;
	while (num[head]==1) head++;
	Count(head);
	memset(g,255,sizeof(g));
	x=King(head,p);
	for (i=1;i<=n;i++)
		if (num[i]-num[a[i]->bro->x]==p){ 
		    x=Min(x,1);break;	
		}
    fprintf(outp,"%d\n",x);
	fclose(outp);
}