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

左儿子又兄弟的转发一定要掌握啊，竞赛必用，主要是降低编程复杂度，省时间。个人觉得状压DP也是为了降低编程复杂度。

方程就不说了，程序应该能看得懂，用的记忆化搜索，方便理解。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 bool p[];

 int N,K,point[],next[],v[],c[],w[],cnt=;

 int f[][][],l[],r[],dist[];

 void insect(int x,int y,int z)

 {next[cnt]=point[x];point[x]=cnt;v[cnt]=y;c[cnt]=z;cnt++;}

 void dfs(int x)

 {

     int i,j;

     for (i=point[x];i!=-;i=next[i])

      if (p[v[i]]==)

      {

          if (l[x]==) l[x]=v[i],dist[v[i]]=dist[x]+c[i]; else

         {

             j=l[x];

             while (r[j]!=) j=r[j];

             r[j]=v[i]; dist[v[i]]=dist[x]+c[i];

         }p[v[i]]=;

      }

     i=l[x]; while (i!=){dfs(i);i=r[i];}

 }

 int dp(int x,int fa,int k)

 {

     if (x==) return ;

     if (f[x][fa][k]!=-) return f[x][fa][k];

     if (k==) {

                 int now=(dist[x]-dist[fa])*w[x];

                 if (l[x]!=) now+=dp(l[x],fa,k);

                 if (r[x]!=) now+=dp(r[x],fa,k);

                 f[x][fa][k]=now; return now;

               }

     int i;f[x][fa][k]=;

     for (i=;i<=k;++i)

      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]));

     for (i=;i<k;++i)

      f[x][fa][k]=min(f[x][fa][k],dp(l[x],x,i)+dp(r[x],fa,k--i));

     return f[x][fa][k];

 }

 int main()

 {

     memset(point,-,sizeof(point));

     memset(next,-,sizeof(next));

     memset(dist,,sizeof(dist));

     memset(v,-,sizeof(v));

     memset(f,-,sizeof(f));

     memset(c,,sizeof(c));

     memset(w,,sizeof(w));

     memset(l,,sizeof(l));

     memset(r,,sizeof(r));

     memset(p,,sizeof(p));

     scanf("%d %d\n",&N,&K);

     int i,di,vi;

     for (i=;i<=N;++i)

     {

         scanf("%d %d %d\n",&w[i],&vi,&di);

         insect(i,vi,di);insect(vi,i,di);

     }p[]=;dfs();

     printf("%d\n",dp(l[],,K));

     return ;

 }