[HDU2196] Computer(트리 dp)

4401 단어 dpHDU

제목 설명


전송문 제목: 나무의 점 하나하나에서 가장 먼 점까지의 거리를 구하세요.

문제풀이


비교적 고전적인 나무 모양 dp.나무의 지름 그 문제를 보았다면 dp 방법은 아주 좋았을 것이다 YY.maxn 및maxn은 점 i에서 하위 트리까지의 점 거리의 최대치와 차대치를 나타내고 f와 g는 점 i에서 하위 트리까지의 점 거리의 최대치와 하위 트리의 점이 아닌 점까지의 거리를 나타낸다.미루는 동안 그림 그려봐. YY.

코드

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_n=1e4+5;
const int max_e=max_n*2;

int n,x,y,z;
int tot,point[max_n],nxt[max_e],v[max_e],c[max_e];
int maxn[max_n],_maxn[max_n],f[max_n],g[max_n],ans[max_n];

inline void clear(){
    tot=0;memset(point,0,sizeof(point));memset(nxt,0,sizeof(nxt));memset(v,0,sizeof(v));
    for (int i=1;i<=n;++i) maxn[i]=_maxn[i]=f[i]=g[i]=ans[i]=0;
}
inline void add(int x,int y,int z){++tot;nxt[tot]=point[x];point[x]=tot;v[tot]=y;c[tot]=z;}
inline void treedp(int x,int fa){
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa){
        treedp(v[i],x);
        if (maxn[x]<maxn[v[i]]+c[i]){
            _maxn[x]=maxn[x];
            maxn[x]=maxn[v[i]]+c[i];
        }
        else _maxn[x]=max(_maxn[x],maxn[v[i]]+c[i]);
      }
}
inline void get_ans(int x,int fa){
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa){
        f[v[i]]=maxn[v[i]];

        if (maxn[v[i]]+c[i]==maxn[x])
          g[v[i]]=c[i]+max(g[x],_maxn[x]);
        else
          g[v[i]]=c[i]+ans[x];

        ans[v[i]]=max(f[v[i]],g[v[i]]);
        get_ans(v[i],x);
      }
}
int main(){
    while (scanf("%d",&n)!=EOF){
        clear();
        for (int i=2;i<=n;++i) scanf("%d%d",&x,&y),add(x,i,y),add(i,x,y);
        treedp(1,0);
        f[1]=ans[1]=maxn[1];
        get_ans(1,0);
        for (int i=1;i<=n;++i)
          printf("%d
"
,ans[i]); } }

좋은 웹페이지 즐겨찾기