hdu 3593 树形依赖背包的优化

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<sstream>
#include<string>
#include<climits>
#include<set>
#include<bitset>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#define iinf 1000000000
#define linf 1000000000000000000LL
#define dinf 1e200
#define all(v) (v).begin(),(v).end()
#define sz(x) x.size()
#define pb push_back
#define mp make_pair
#define lng long long
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define pll pair<lng,lng>
#define pss pair<string,string>
#define pdd pair<double,double>
#define X first
#define Y second
#define pi 3.14159265359
#define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i)
#define ffd(i,n) for(int i=xi;i>=(int)(n);--i)
#define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next)
#define cc(i,j) memset(i,j,sizeof(i))
#define N 100001
#define M 200010
using namespace std;
typedef vector<int> vi;
typedef vector<string> vs;
typedef unsigned int uint;
typedef unsigned lng ulng;
//Numberic Functions
template<class T> inline T gcd(T a,T b)//NOTES:gcd(
{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm(
{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
template<class T> inline T euclide(T a,T b,T &x,T &y)//NOTES:euclide(
{if(a<0){T d=euclide(-a,b,x,y);x=-x;return d;}
if(b<0){T d=euclide(a,-b,y);y=-y;return d;}
if(b==0){x=1;y=0;return a;}else{T d=euclide(b,a%b,y);T t=x;x=y;y=t-(a/b)*y;return d;}}
template<class T> inline vector<pair<T,int> > factorize(T n)//NOTES:factorize(
{vector<pair<T,int> > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));}
i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;}
template<class T> inline bool isPrimeNumber(T n)//NOTES:isPrimeNumber(
{if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
template<class T> inline T eularFunction(T n)//NOTES:eularFunction(
{vector<pair<T,int> > R=factorize(n);T r=n;for (int i=0;i<R.size();i++)r=r/R[i].first*(R[i].first-1);return r;}
template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;}
template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;}
template<class T> inline T Min(T x,T y){return (x>y?y:x);}
template<class T> inline T Max(T x,T y){return (x<y?y:x);}
struct pp{int v,next;}edge[2*N];int tot=0,n,m,val[N],cost[N],pos[N],dp[510][10001],p,head[N],ans;
inline void addedge(int u,int v){edge[tot].v=v,edge[tot].next=head[u],head[u]=tot++;}
void dfs(int r,int cap)
{
ffl(o,r)
{ int v=edge[o].v;
ff(i,cap) dp[pos[v]][i]=dp[pos[r]][i];
dfs(v,cap-cost[v]);
ff(i,cost[v],cap) checkmax(dp[pos[r]][i],dp[pos[v]][i-cost[v]]+val[v]);
}
}
int main()
{
#ifdef DEBUG
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
#endif
while(scanf("%d%d",&n,&m)==2)
{
cc(head,-1);cc(pos,0);cc(dp,0);tot=0,p=1,pos[0]=1,ans=0,cost[0]=0,val[0]=0;
ff(i,1,n){int fa;scanf("%d%d%d",&cost[i],&val[i],&fa);if(fa==i) addedge(0,i);else { if(pos[fa]==0)pos[fa]=++p;addedge(fa,i);}}
dfs(0,m);printf("%dn",dp[1][m]);
}
return 0;
}
/*
made by qinggege
*

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!