poj3249 拓扑排序+DP
题意:给出一个有向无环图,每个顶点都有一个权值。求一条从入度为0的顶点到出度为0的顶点的一条路径,路径上所有顶点权值和最大。 思路:因为是无环图,则对于每个点经过的路径求其最大权值有,dp[i]=max(dp[j]) j为i的子节点集合。再根据其要求入度为零为顶点,可以用拓扑排序每次枚举入度为零的点删去找下一个入度为零的点进行dp。 代码:#include #includ