刚开始想用矩阵模拟邻接链表的, MLE, 就改成暴力DP了.
#include<iostream> #define max(a,b) a>b?a:b using namespace std; int n; int T[6001][2]; int f[6001]; int up[6001]; void find(int p); int main() { int i,j,k; memset(up,false,sizeof(up)); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&f[i]); while(scanf("%d%d",&j,&k)&&j&&k) up[j]=k; for(i=1;i<=n;i++) if(!up[i]) break; find(i); printf("%d/n",max(T[i][0],T[i][1])); return 0; } void find(int p) { int i,j,k; T[p][1]=f[p]; for(i=1;i<=n;i++) { if(up[i]==p) { find(i); T[p][0]+=max(T[i][0],T[i][1]); T[p][1]+=T[i][0]; } } return; }
