首页 > 代码库 > P1352 没有上司的舞会
P1352 没有上司的舞会
题目描述
某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入输出格式
输入格式：
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0 0
输出格式：
输出最大的快乐指数。
输入输出样例
输入样例#1：
711111111 32 36 47 44 53 50 0
我们用dp[i][0]表示这个点不参加
用dp[i][1]表示这个点参加
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=6001; 8 void read(int &n) 9 {10 char c=‘+‘;int x=0;bool flag=0;11 while(c<‘0‘||c>‘9‘)12 {c=getchar();if(c==‘-‘)flag=1;}13 while(c>=‘0‘&&c<=‘9‘)14 {x=x*10+(c-48);c=getchar();}15 flag==1?n=-x:n=x;16 }17 int n;18 int ha[MAXN];19 int fa[MAXN];20 int ch[MAXN];21 int dp[MAXN][3];22 int deg[MAXN];23 int ans=0;24 void Topsort()25 {26 queue<int>q;27 for(int i=1;i<=n;i++)28 if(deg[i]==0)29 q.push(i);30 while(q.size()!=0)31 {32 int p=q.front();33 q.pop();34 deg[fa[p]]--;35 if(deg[fa[p]]==0&&fa[p]!=-1)36 q.push(fa[p]);37 dp[fa[p]][0]+=max(dp[p][0],dp[p][1]);38 // 上司不参加 39 dp[fa[p]][1]+=dp[p][0];40 // 参加 41 if(fa[p]==-1)42 ans+=max(dp[fa[p]][1],dp[fa[p]][0]);43 }44 printf("%d",ans);45 46 }47 int main()48 {49 read(n);50 memset(ch,-1,sizeof(ch));51 memset(fa,-1,sizeof(fa));52 for(int i=1;i<=n;i++)53 read(ha[i]);54 for(int i=1;i<=n;i++)dp[i][1]=ha[i];55 for(int i=1;i<=n;i++)56 {57 int x,y;58 read(x);read(y);59 fa[x]=y;60 ch[y]=x;61 deg[y]++;62 }63 Topsort();64 return 0;65 }
P1352 没有上司的舞会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。