HDU 2196 Computer

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2196

题目翻译

一个N个节点的树，每条边长度，求每个节点到距其最远的节点的距离。

题解

以1为根，分别求出以i为根的子树中距i最长的距离和经过i的父亲的最长距离，答案就是这两个值求Max

代码

/*
  Author:WNJXYK
  Web:http://wnjxyk.cn
  Problem:Hdu 2196
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int Maxn=10000;
struct Edge{
    int v,nxt,w;
    Edge(){}
    Edge(int v0,int n0,int w0){
        v=v0;
        nxt=n0;
        w=w0;
    }
};
Edge e[Maxn*2+5];
int head[Maxn+5];
int nume;
inline void addEdge(int x,int y,int w){
    e[++nume]=Edge(y,head[x],w);
    head[x]=nume;
}
int downLen[Maxn+5][2];
int upLen[Maxn+5];
void updateDownLen(int x,int len){
    if (len>downLen[x][0]){
        downLen[x][1]=downLen[x][0];
        downLen[x][0]=len;
    }else if (len>downLen[x][1]){
        downLen[x][1]=len;
    }
}
void DP1(int x,int fa){
    //printf("#%d FA=%d\n",x,fa);
    downLen[x][0]=downLen[x][1]=0;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if (v==fa) continue;
        DP1(v,x);
        updateDownLen(x,downLen[v][0]+w);
    }
}
void DP2(int x,int fa,int len){
    upLen[x]=0;
    if (fa!=0){
        int udLen,uuLen;
        udLen=len+(downLen[fa][0]!=len+downLen[x][0]?downLen[fa][0]:downLen[fa][1]);
        uuLen=len+upLen[fa];
        //printf("#%d UP %d %d\n",x,udLen,uuLen);
        upLen[x]=max(udLen,uuLen);
    }
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if (fa!=v)DP2(v,x,w);
    }
}
int n;
inline void solve(){
    nume=0;
    memset(head,0,sizeof(head));
    for (int i=2;i<=n;i++){
        int y,w;
        scanf("%d%d",&y,&w);
        addEdge(i,y,w);
        addEdge(y,i,w);
    }
    DP1(1,0);
    DP2(1,0,0);
    //for (int i=1;i<=n;i++)printf("#%d D1:%d D2:%d UP:%d\n",i,downLen[i][0],downLen[i][1],upLen[i]);
    for (int i=1;i<=n;i++)
        printf("%d\n",max(downLen[i][0],upLen[i]));
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n)!=EOF) solve();
    return 0;
}

Author:WNJXYK

Web:http://wnjxyk.cn

Problem:Hdu 2196

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define LL long long

using namespace std;

const int Maxn=10000;

struct Edge{

int v,nxt,w;

Edge(){}

Edge(int v0,int n0,int w0){

v=v0;

nxt=n0;

w=w0;

}

};

Edge e[Maxn*2+5];

int head[Maxn+5];

int nume;

inline void addEdge(int x,int y,int w){

e[++nume]=Edge(y,head[x],w);

head[x]=nume;

}

int downLen[Maxn+5][2];

int upLen[Maxn+5];

void updateDownLen(int x,int len){

if (len>downLen[x][0]){

downLen[x][1]=downLen[x][0];

downLen[x][0]=len;

}else if (len>downLen[x][1]){

downLen[x][1]=len;

}

void DP1(int x,int fa){

//printf("#%d FA=%d\n",x,fa);

downLen[x][0]=downLen[x][1]=0;

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v,w=e[i].w;

if (v==fa) continue;

DP1(v,x);

updateDownLen(x,downLen[v][0]+w);

}

void DP2(int x,int fa,int len){

upLen[x]=0;

if (fa!=0){

int udLen,uuLen;

udLen=len+(downLen[fa][0]!=len+downLen[x][0]?downLen[fa][0]:downLen[fa][1]);

uuLen=len+upLen[fa];

//printf("#%d UP %d %d\n",x,udLen,uuLen);

upLen[x]=max(udLen,uuLen);

}

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v,w=e[i].w;

if (fa!=v)DP2(v,x,w);

}

int n;

inline void solve(){

nume=0;

memset(head,0,sizeof(head));

for (int i=2;i<=n;i++){

int y,w;

scanf("%d%d",&y,&w);

addEdge(i,y,w);

addEdge(y,i,w);

}

DP1(1,0);

DP2(1,0,0);

//for (int i=1;i<=n;i++)printf("#%d D1:%d D2:%d UP:%d\n",i,downLen[i][0],downLen[i][1],upLen[i]);

for (int i=1;i<=n;i++)

printf("%d\n",max(downLen[i][0],upLen[i]));

}

int main(){

//freopen("in.txt","r",stdin);

//freopen("out.txt","w",stdout);

while(scanf("%d",&n)!=EOF) solve();

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑