HDU-1520-Anniversary party
http://acm.hdu.edu.cn/showproblem.php?pid=1520
DFS,有些节点具有父子关系,要求具有父子关系的节点不能同时出现
#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;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
算法-确定比赛名次(HDU-1285).rar
最短路(HDU-2544).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar
算法-六度分离(HDU-1869)(包含源程序).rar
算法-排列组合(HDU-1521)(包含源程序).rar