首页 > > 程序设计 > C/C++ >

Computer HDU - 2196

2018-06-17 21:41:01来源：未知阅读 ()

Computer HDU - 2196

题意：求以树上任一点为端点的最长链。注意，读入的不是边表，而是每个节点（除了1号，它是根节点）的父亲和与父亲间边的长度。

方法：

从每个端点出发的最长链，第一种是向下（向子节点）走，第二种是向父节点走。分别处理即可。（具体看程序）

（感觉做法一点也不优美....最长链次长链什么鬼...）

错误（本地）：少了23行，没有将原来最长链更新到次长链上

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 struct Edge
 6 {
 7     int to,next,w;
 8 }e[20100];
 9 int f1[10100],ne,fa[10100],a1[10100],a2[10100],b1[10100],ww[10100],b2[10100],ansu[10100];
10 //a1[i],b1[i]分别记录节点i向下最长链的长度，节点i向下最长链所经过的i的子节点编号
11 //a2[i],b2[i]分别记录节点i向下次长链的长度（保证除了节点i以外，不与最长链有公共节点），节点i向下次长链所经过的自身的子节点编号
12 //ww[i]记录节点i到父节点的边的权值
13 //ansu[i]记录节点i向上走的最长链
14 int n;
15 void dfs(int x,int fa)
16 {
17     for(int k=f1[x];k!=0;k=e[k].next)
18         if(e[k].to!=fa)
19         {
20             dfs(e[k].to,x);//先求出子节点向下的a1,b1,a2,b2,再用子节点的来更新自身的
21             if(a1[e[k].to]+e[k].w>a1[x])//如果比已知最长链长
22             {
23                 a2[x]=a1[x],b2[x]=b1[x];//那么新的次长链就是已知最长链
24                 a1[x]=a1[e[k].to]+e[k].w,b1[x]=e[k].to;//新的最长链就是自身指向这个子节点的边再加上子节点向下的最长链形成的链
25             }
26             else if(a1[e[k].to]+e[k].w>a2[x])//如果不比已知最长链长，但比已知次长链长
27                 a2[x]=a1[e[k].to]+e[k].w,b2[x]=e[k].to;//新的次长链就是自身指向这个子节点的边再加上子节点向下的最长链形成的链
28         }
29 }
30 void dfs2(int x,int fa)//分别为当前节点编号和当前节点父亲编号
31 {
32     if(fa!=0)//如果为根节点，那么没有向上的链，否则就有
33     {
34         int t1;
35         if(x==b1[fa])
36             t1=a2[fa];
37         else
38             t1=a1[fa];//t1表示父亲节点向下的最长链长度。如果父亲节点向下的最长链经过x，那么t1变为父亲节点向下的次长链长度
39             //就是父亲节点的向下的不经过x的最长链长度
40         ansu[x]=max(t1,ansu[fa])+ww[x];
41         //当前节点向上的最长链，就是当前节点指向父亲的边再加上父亲节点向上的最长链形成的链，与当前节点指向父亲的边加上t1形成的链，其中较长的一条
42     }
43     for(int k=f1[x];k!=0;k=e[k].next)
44         if(e[k].to!=fa)
45             dfs2(e[k].to,x);//这一次要先求出父节点的才能求出子节点的，与第一个dfs()不一样
46 }
47 int main()
48 {
49     int i,x,y;
50     while(scanf("%d",&n)==1)
51     {
52         ne=0;
53         memset(f1,0,sizeof(f1));
54         memset(fa,0,sizeof(fa));
55         memset(a1,0,sizeof(a1));
56         memset(a2,0,sizeof(a2));
57         memset(ansu,0,sizeof(ansu));
58         for(i=2;i<=n;i++)
59         {
60             scanf("%d%d",&x,&y);
61             e[++ne].to=x;
62             e[ne].next=f1[i];
63             e[ne].w=y;
64             f1[i]=ne;
65             e[++ne].to=i;
66             e[ne].next=f1[x];
67             e[ne].w=y;
68             f1[x]=ne;
69             ww[i]=y;
70         }
71         dfs(1,0);//求出所有节点向下走的最长链与次长链
72         dfs2(1,0);//求出所有节点向上走的最长链
73         for(i=1;i<=n;i++)
74             printf("%d\n",max(a1[i],ansu[i]));//最后答案就是某个点向下、向上走的最长链中较长的一条
75     }
76     
77     return 0;
78 }