题面
题意:一个派对里有n个人,n个人之间有着一张上下级关系图,派对要求上级和下级不能同时出现,而每个人都有一个rating值,要求选择哪些人到场能使rating值之和最大
思路:
1.每个人有两种状态-出席或不出席
2.上级出席那么其直接对应的下级不能出席,下级出席则其直接对应的上级不能出席
代码：
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; const int N=1e4+5; struct E { int val; int next; } edge[5*N+10]; int head[N],vis[N],c,dp[N][2],con[N]; int selMax(int x,int y) { return x>=y?x:y; } void add(int x,int y) { edge[c].val=y; edge[c].next=head[x]; head[x]=c; c+=1; } void DFS(int root) { dp[root][1]=con[root]; dp[root][0]=0; vis[root]=1; for(int i=head[root]; i!=-1; i=edge[i].next) { int cur=edge[i].val; if(!vis[cur]) { DFS(cur); dp[root][1]+=dp[cur][0]; dp[root][0]+=selMax(dp[cur][1],dp[cur][0]); } } } int main() { int n; while(~scanf("%d",&n)) { for(int i=1; i<=n; i+=1){ scanf("%d",&con[i]); } memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); int u,v; c=0; while(true) { scanf("%d%d",&u,&v); if(u+v==0) break; add(v,u); add(u,v); } DFS(1); printf("%d\n",selMax(dp[1][0],dp[1][1])); } return 0; }
