HDU-1520-Anniversary party
DFS，有些节点具有父子关系，要求具有父子关系的节点不能同时出现
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 6001
struct node //左二子右兄弟法建树
{
int parent;
int child;
int brother;
int attend;
int notattend;
int Max()
{
return attend>notattend?attend:notattend;
}
void init()
{
parent=0;
child=0;
brother=0;
notattend=0;
}
}p[N];
void dfs(int x)
{
int child;
child=p[x].child;
while(child)
{
dfs(child);
p[x].attend+=p[child].notattend;
p[x].notattend+=p[child].Max();
child=p[child].brother;
}
}
int main()
{
int i,n,a,b;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
p[i].init();
scanf("%d",&p[i].attend);
}
while(scanf("%d%d",&a,&b),a||b)
{
p[a].parent=b;
p[a].brother=p[b].child;
p[b].child=a;
}
for(i=1;i<=n;i++)
if(p[i].parent==0)
{
dfs(i);
printf("%d\n",p[i].Max());
break;
}
}
return 0;
}
补充：软件开发 , C++ ,
