Vijos p1518 河流 转二叉树左儿子又兄弟

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 bool p[103];
 6 int N,K,point[103],next[203],v[203],c[203],w[103],cnt=0;
 7 int f[103][103][103],l[103],r[103],dist[103];
 8 void insect(int x,int y,int z)
 9 {next[cnt]=point[x];point[x]=cnt;v[cnt]=y;c[cnt]=z;cnt++;}
10 void dfs(int x)
11 {
12     int i,j;
13     for (i=point[x];i!=-1;i=next[i])
14      if (p[v[i]]==0)
15      {
16          if (l[x]==0) l[x]=v[i],dist[v[i]]=dist[x]+c[i]; else
17         {
18             j=l[x];
19             while (r[j]!=0) j=r[j];
20             r[j]=v[i]; dist[v[i]]=dist[x]+c[i];
21         }p[v[i]]=1;
22      }
23     i=l[x]; while (i!=0){dfs(i);i=r[i];}
24 }
25 int dp(int x,int fa,int k)
26 {
27     if (x==0) return 0;
28     if (f[x][fa][k]!=-1) return f[x][fa][k];
29     if (k==0) {
30                 int now=(dist[x]-dist[fa])*w[x];
31                 if (l[x]!=0) now+=dp(l[x],fa,k);
32                 if (r[x]!=0) now+=dp(r[x],fa,k);
33                 f[x][fa][k]=now; return now;
34               }
35     int i;f[x][fa][k]=2000000001;
36     for (i=0;i<=k;++i)
37      f[x][fa][k]=min(f[x][fa][k],dp(l[x],fa,i)+dp(r[x],fa,k-i)+w[x]*(dist[x]-dist[fa]));
38     for (i=0;i<k;++i)
39      f[x][fa][k]=min(f[x][fa][k],dp(l[x],x,i)+dp(r[x],fa,k-1-i));
40     return f[x][fa][k];
41 }
42 int main()
43 {
44     memset(point,-1,sizeof(point));
45     memset(next,-1,sizeof(next));
46     memset(dist,0,sizeof(dist));
47     memset(v,-1,sizeof(v));
48     memset(f,-1,sizeof(f));
49     memset(c,0,sizeof(c));
50     memset(w,0,sizeof(w));
51     memset(l,0,sizeof(l));
52     memset(r,0,sizeof(r));
53     memset(p,0,sizeof(p));
54     scanf("%d %d\n",&N,&K);
55     int i,di,vi;
56     for (i=1;i<=N;++i)
57     {
58         scanf("%d %d %d\n",&w[i],&vi,&di);
59         insect(i,vi,di);insect(vi,i,di);
60     }p[0]=1;dfs(0);
61     printf("%d\n",dp(l[0],0,K));
62     return 0;
63 }