题目的意思就是求图的中心，即到最远结点的距离最近。
具体做法为：建立一棵树；求出每个结点向下的最大深度和次大深度，其中定义最大深度路径和次大深度路径没有公共边，之所以要求次大深度，是为了在下一步，当求结点i向上的最长路径时，避免father[i]向下的路径不经过i结点；求出每个结点向上的最长路径；取向下和向上中较大的一个。
以下是我的代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct NODE
{
long son;
struct NODE *next;
}SON;
long n;
long father[10001];
SON *son[10001];
long down[10001][2]={0},up[10001]={0};
void insert(SON *link,long x)
{//------将第x个结点设为*link的儿子
SON *p;
p=(SON*)malloc(sizeof(SON));
p->son=x;
p->next=link->next;
link->next=p;
}
void init()
{
FILE *fin=fopen("net.in","r");
long i,w;
fscanf(fin,"%ld",&n);
for(i=1;i<=n;i++)
{
son[i]=(SON*)malloc(sizeof(SON));
son[i]->son=0;
son[i]->next=NULL;
}
for(i=2;i<=n;i++)
{
fscanf(fin,"%ld",&w);
insert(son[w],i);
father[i]=w;
}
fclose(fin);
}
void dp1(long k)
{
SON *p;
long i;
p=son[k]->next;
while(p!=NULL)
{
i=p->son;
dp1(i);
if(down[i][0]+1>down[k][0])
{
down[k][1]=down[k][0];
down[k][0]=down[i][0]+1;
}
else
{
if(down[i][0]+1>down[k][1])
down[k][1]=down[i][0];
}
p=p->next;
}
}
void dp2(long k)
{
SON *p;
long t;
if(k>=2)
{
up[k]=up[father[k]]+1;
if(down[father[k]][0]==down[k][0]+1)
t=down[father[k]][1]+1;
else t=down[father[k]][0]+1;
if(t>up[k])
up[k]=t;
}
p=son[k]->next;
while(p!=NULL)
{
dp2(p->son);
p=p->next;
}
}
void write()
{
FILE *fout=fopen("net.out","w");
long i,t,min=2000000000;
for(i=1;i<=n;i++)
{
if(up[i]<down[i][0])
t=down[i][0];
else t=up[i];
if(t<min)
min=t;
}
for(i=1;i<=n;i++)
{
if(up[i]<down[i][0])
t=down[i][0];
else t=up[i];
if(t==min)
fprintf(fout,"%ld ",i);
}
fprintf(fout,"\n");
fclose(fout);
}
int main()
{
init();
dp1(1);
dp2(1);
write();
return 0;
}
posted on 2010-01-06 19:27
lee1r 阅读(223)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划