xfstart07
Get busy living or get busy dying

treeDP:
#include<iostream>
using namespace std;

int N;
int father[10100];
int pre[10100],son[10100],now[10100]={0};
int down[10100][2]={0};
int up[10100]={0};
void dfs(int x){
    
int Now=now[x];
    
while(Now>0){
        
int k=son[Now];
        dfs(k);
        
if(down[k][1]+1>down[x][1]){
            down[x][
0]=down[x][1];  //次优值
            down[x][1]=down[k][1]+1;  //最优值
        }
        
else if(down[k][1]+1>down[x][0])
            down[x][
0]=down[k][1]+1;
        Now
=pre[Now];
    }
}
void treedp(int x){
    
if(x==1) up[x]=0;
    
else{
        up[x]
=up[father[x]]+1;
        
int tmp;
        
if(down[father[x]][1]==down[x][1]+1)  //当father[x]的最优值是从x来的,则从另一条取值
            tmp=down[father[x]][0]+1;
        
else tmp=down[father[x]][1]+1;
        
if(tmp>up[x]) 
            up[x]
=tmp;
    }
    
while(now[x]){
        treedp(son[now[x]]);
        now[x]
=pre[now[x]];
    }    
}
int main()
{
    cin
>>N;
    
int c=0,x;
    
for(int i=2;i<=N;++i){
        cin
>>x;
        father[i]
=x;
        
++c; pre[c]=now[x]; son[c]=i; now[x]=c;
    }
    dfs(
1);
    treedp(
1);
    
int Min=0xFFFFFFF,ch1,ch2;
    
for(int i=1;i<=N;++i){
        
int tmp=max(up[i],down[i][1]);
        
if(Min>tmp){
            Min
=tmp;
            ch1
=i;
            ch2
=0;
        }
        
else if(Min==tmp)
            ch2
=i;
    }
    cout
<<ch1;
    
if(ch2) cout<<" "<<ch2;
    cout
<<endl;
    
return 0;
}


BFS:
#include<iostream>
using namespace std;

int N;
int que[20001];
int dis[20001]={0};
int a[20001];
int pre[20001]={0};
bool vis[20001]={0};
int mx=0,mx2=0,mxi,mx2i;
int main()
{
    cin
>>N;
    
for(int i=2;i<=N;++i)
        cin
>>a[i];
    que[
1]=1;
    
int h=1,t=1;
    
while(h<=t){
        
for(int i=1;i<=N;++i)
            
if(a[i]==que[h]&&dis[i]==0){
                dis[i]
=dis[que[h]]+1;
                
if(dis[i]>mx){
                    mx
=dis[i];
                    mxi
=i;
                }
                que[
++t]=i;
            }
        h
++;
    }
    memset(dis,
0,sizeof(dis));
    que[
1]=mxi;
    vis[mxi]
=1;
    h
=t=1;
    
while(h<=t){
        
int x=que[h];
        
if(x!=1&&!vis[a[x]]){
            que[
++t]=a[x];
            dis[a[x]]
=dis[x]+1;
            pre[a[x]]
=x;
            vis[a[x]]
=1;
            
if(dis[a[x]]>mx2){
                mx2
=dis[a[x]];
                mx2i
=a[x];
            }
        }
        
for(int i=1;i<=N;++i)
                
if(a[i]==x&&dis[i]==0&&!vis[i]){
                    dis[i]
=dis[x]+1;
                    pre[i]
=x;
                    vis[i]
=1;
                    
if(dis[i]>mx2){
                        mx2
=dis[i];
                        mx2i
=i;
                    }
                    que[
++t]=i;
                }
        h
++;
    }
    
int i=pre[mx2i]; t=0;
    
while(i!=mxi){
        
++t;
        i
=pre[i];
    }
    
if(t==0)
        cout
<<mx2i<<" "<<mxi;
    i
=pre[mx2i];
    
int p,q;
    
if(t%2){
        p
=(t/2)+1;
        q
=0;
    }
    
else{
        p
=t/2;
        q
=p+1;
    }
    t
=0;
    
while(i!=mxi){
        
++t;
        
if(t==p) cout<<i;
        
if(t==q) cout<<" "<<i;
        i
=pre[i];
    }
    cout
<<endl;
    
return 0;
}


posted on 2009-06-04 20:15 xfstart07 阅读(146) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理