TELE POJ 1155

状态转移方程: dp[v][1] = Money[v]; (v为叶子节点)

                          dp[v][j] = max(dp[v][j],dp[v][j-i] + dp[k][i] - len);(v为非叶子节点,j表示用户个数,i为容量，k为v的子节点,len为边权)

    算法复杂度O(sum(num[i],num[s])) (num[i]为某个节点的叶子子孙个数，num[s]为i的子节点的叶子子孙个数)

#include
#include
#include
using namespace std;const int maxn=3010;
const int INF=(1<<28);int N,M;
struct Node{int v;int c;
};
vectormap[maxn];
int val[maxn];
int dp[maxn][maxn];int Max(int a,int b){if(a=0;j--){for(k=0;k<=num && k<=j;k++){dp[u][j]=Max(dp[u][j],dp[u][j-k]+dp[v][k]-map[u][i].c);}}		}return sum;
}int main()
{int i,j;int K,a,b;Node tmp;while(scanf("%d%d",&N,&M)!=EOF){for(i=0;i<=N;i++)map[i].clear();for(i=1;i<=N-M;i++){scanf("%d",&K);for(j=0;j=0;i--)if(dp[1][i]>=0){ans=i;break;}printf("%d\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！