題目的意思就是求圖的中心，即到最遠結點的距離最近。
具體做法為：建立一棵樹；求出每個結點向下的最大深度和次大深度，其中定義最大深度路徑和次大深度路徑沒有公共邊，之所以要求次大深度，是為了在下一步，當求結點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 閱讀(244)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃