题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1520
题意大致是给出一个隶属关系树, 每个人代表一个结点, 每个结点都有权值, 有父子关系的点对只能选择一个, 问怎样使得权值之和最大.
代码如下:
- #include<bits/stdc++.h>
- using namespace std;
- typedef unsigned int ui;
- typedef long long ll;
- typedef unsigned long long ull;
- #define pf printf
- #define mem(a,b) memset(a,b,sizeof(a))
- #define prime1 1e9+7
- #define prime2 1e9+9
- #define pi 3.14159265
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define scand(x) scanf("%llf",&x)
- #define f(i,a,b) for(int i=a;i<=b;i++)
- #define scan(a) scanf("%d",&a)
- #define mp(a,b) make_pair((a),(b))
- #define P pair<int,int>
- #define dbg(args) cout<<#args<<":"<<args<<endl;
- #define inf 0x7ffffff
- inline int read(){
- int ans=0,w=1;
- char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
- while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
- return ans*w;
- }
- int n,m,t;
- const int maxn=1e4+10;
- int value[maxn];
- int dp[maxn][2];//0 表示这个点不选择的最大权值和, 1 表示选择这个点的最大权值和
- vector<int> G[maxn];
- int f[maxn];//f 的设置是为了查找根节点
- void dfs(int u)
- {
- dp[u][0]=0;
- dp[u][1]=value[u];// 参加和不参加两种情况的初值设置
- for(int i=0;i<G[u].size();i++)
- {
- int son=G[u][i];
- dfs(son);// 对每一个子节点都进行一次 dfs
- dp[u][0]+=max(dp[son][1],dp[son][0]);// 父节点不选择之后子节点可选可不选
- dp[u][1]+=dp[son][0];// 父节点选择之后子节点只能不选择
- }
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- std::iOS::sync_with_stdio(false);
- while(~scanf("%d",&n))
- {
- f(i,1,n)
- {
- scanf("%d",&value[i]);
- G[i].clear();
- f[i]=-1;
- }
- while(1)
- {
- int a,b;
- scanf("%d%d",&a,&b);
- if(a==0&&b==0)break;
- G[b].push_back(a);
- f[a]=b;
- }
- int t=1;
- while(f[t]!=-1)
- {
- t=f[t];
- }
- dfs(t);
- printf("%d\n",max(dp[t][0],dp[t][1]));
- }
- }
来源: http://www.bubuko.com/infodetail-3502578.html