Description
There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.
Input
Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output
Output should contain the maximal sum of guests' ratings.
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
hdu2412Party at Hali-Bula【树型DP入门题】
居然是多组输入 坑爹啊啊啊啊
可以加虚拟大boss也可以不加
| 1876 | 140 |
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mm=6002;
int head[mm],nxt[mm],ver[mm];
/**head[i]表示第i个人指向的链表头*/
/**ver[i]表示链表中的数值*/
/**nxt[i]表示链表元素的下一个元素*/
int f[mm][2];
/**f[i][0]表示不选这个员工时，它和它整个下属的最大幽默系数*/
/**f[i][1]表示选这个员工时，它和它整个下属的最大幽默系数*/
int w[mm];/**w[i]表示第i个人的幽默指数*/
bool c[mm];/**c[i]标记第i个人是否有老板*/
// char name[mm][22],s1[22],s2[22];/**name[i]表示第i个人的名字,s1,s2用来读入名字*/
int n,size,edge;/**n表示多少条读入，size表示已编号人数，edge表示关系边数*/
int max(int x,int y){if(x>y)return x;return y;}
void addedge(int u,int v)/**建立关系边，这个是用数组模拟指针链表，效率会高一点，也好写一点*/
{
ver[edge]=v,nxt[edge]=head[u],head[u]=edge++;
/**给u的链表增加元素,具体自己手动试一下就明白了*/
}
//// int getID(char a[])/**给名字编号*/
//// {
//// for(int i=1;i<=size;++i)/**查看是否编过好号，编过直接退出编号*/
//// if(strcmp(a,name[i])==0)return i;
//// strcpy(name[++size],a);/**给它编个号*/
//// return size;/**返回编号*/
//// }
void treeDP(int u)/**树型DP，一般都是以搜索的形式来做*/
{
f[u][0]=0;/**没选这个人可能幽默值是0*/
f[u][1]=w[u];/**选这个人幽默值至少为他自己*/
for(int i=head[u],v/**i等价于指针*/;i>=0;i=nxt[i])/**枚举u的链表，也就是他的下属*/
{
treeDP(v=ver[i]);/**先取得下属的f[v][0],f[v][1]的值，以便递推*/
f[u][0]+=max(f[v][0],f[v][1]);/**如果u不选的话，他的下属可以选也可以不选*/
f[u][1]+=f[v][0];/**如果u选了，它的下属不能选*/
}
}
int main()
{
// freopen("cin.txt","r",stdin);
int i,v,l,k;
while(~scanf("%d",&n))//printf("n=%d\n",n);
{
edge=0;/**一开始没有编号*/
size=n;
memset(c,0,sizeof(c));/**每个人一开始都不知道有没有老板*/
memset(head,-1,sizeof(head));/**头指针赋值为-1表示空*/
for(int i=1;i<=n;i++)
{
scanf("%d",&v);
w[i]=v;
}
while(~scanf("%d%d",&l,&k))
{
if(l==0&&k==0) break;
c[l]=1;
addedge(k,l);
}
// while(n--)/**读入员工信息*/
// {
// scanf("%s %d %s",s1,&v,s2);
// w[getID(s1)]=v;/**给这个员工编号，并记住它的幽默指数*/
// c[getID(s1)]=1;/**这个员工有老板*/
// addedge(getID(s2),getID(s1));/**给他的老板编号，并增加关系边*/
// }
/**虚拟一个公司老总，是所有没有老板的员工的老板*/
w[0]=0;/**它的幽默指数为0，不不干扰答案*/
for(i=1;i<=n;++i)
if(!c[i])addedge(0,i);/**找到没老板的员工，建立关系边*/
treeDP(0);/**树型DP*/
// for(int i=0;i<=n;i++)printf("i=%d,0=%d,1=%d\n",i,f[i][0],f[i][1]);
printf("%d\n",f[0][0]);/**最终老总不能选，输出不选的最大值就是答案*/
}
return 0;
}
| 1908 | 93 |
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int mm=10000;
int head[mm],nxt[mm],ver[mm];
/**head[i]表示第i个人指向的链表头*/
/**ver[i]表示链表中的数值*/
/**nxt[i]表示链表元素的下一个元素*/
int f[mm][2];
/**f[i][0]表示不选这个员工时，它和它整个下属的最大幽默系数*/
/**f[i][1]表示选这个员工时，它和它整个下属的最大幽默系数*/
int w[mm];/**w[i]表示第i个人的幽默指数*/
bool c[mm];/**c[i]标记第i个人是否有老板*/
// char name[mm][22],s1[22],s2[22];/**name[i]表示第i个人的名字,s1,s2用来读入名字*/
int n,size,edge;/**n表示多少条读入，size表示已编号人数，edge表示关系边数*/
int max(int x,int y){if(x>y)return x;return y;}
void addedge(int u,int v)/**建立关系边，这个是用数组模拟指针链表，效率会高一点，也好写一点*/
{
ver[edge]=v,nxt[edge]=head[u],head[u]=edge++;
/**给u的链表增加元素,具体自己手动试一下就明白了*/
}
//// int getID(char a[])/**给名字编号*/
//// {
//// for(int i=1;i<=size;++i)/**查看是否编过好号，编过直接退出编号*/
//// if(strcmp(a,name[i])==0)return i;
//// strcpy(name[++size],a);/**给它编个号*/
//// return size;/**返回编号*/
//// }
void treeDP(int u)/**树型DP，一般都是以搜索的形式来做*/
{
f[u][0]=0;/**没选这个人可能幽默值是0*/
f[u][1]=w[u];/**选这个人幽默值至少为他自己*/
for(int i=head[u],v/**i等价于指针*/;i>=0;i=nxt[i])/**枚举u的链表，也就是他的下属*/
{
treeDP(v=ver[i]);/**先取得下属的f[v][0],f[v][1]的值，以便递推*/
f[u][0]+=max(f[v][0],f[v][1]);/**如果u不选的话，他的下属可以选也可以不选*/
f[u][1]+=f[v][0];/**如果u选了，它的下属不能选*/
}
}
int main()
{
// freopen("cin.txt","r",stdin);
int i,v,l,k;
while(~scanf("%d",&n))//printf("n=%d\n",n);
{
edge=0;/**一开始没有编号*/
size=n;
memset(c,0,sizeof(c));/**每个人一开始都不知道有没有老板*/
memset(head,-1,sizeof(head));/**头指针赋值为-1表示空*/
for(int i=1;i<=n;i++)
{
scanf("%d",&v);
w[i]=v;
}
while(~scanf("%d%d",&l,&k))
{
if(l==0&&k==0) break;
c[l]=1;
addedge(k,l);
}
// while(n--)/**读入员工信息*/
// {
// scanf("%s %d %s",s1,&v,s2);
// w[getID(s1)]=v;/**给这个员工编号，并记住它的幽默指数*/
// c[getID(s1)]=1;/**这个员工有老板*/
// addedge(getID(s2),getID(s1));/**给他的老板编号，并增加关系边*/
// }
/**虚拟一个公司老总，是所有没有老板的员工的老板*/
w[0]=0;/**它的幽默指数为0，不不干扰答案*/
int tt;
for(i=1;i<=n;++i)
if(!c[i])
{
treeDP(tt=i);break;
}
//addedge(0,i);/**找到没老板的员工，建立关系边*/
/**树型DP*/
// for(int i=0;i<=n;i++)printf("i=%d,0=%d,1=%d\n",i,f[i][0],f[i][1]);
printf("%d\n",max(f[tt][0],f[tt][1]));
}
return 0;
}
京公网安备 11010502036488号