River

· · 个人记录 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100+10;
const int K=55;
const ll inf=2000000000+1000;
struct node{
    int nxt,to;
    ll val;
}bian[2*N];
int hd[N],cnt;
int w[N];
int n,k;
ll f[N][N][K];
int fa[N];
int disf[N];
bool vis[N];
void add(int x,int y,ll z)
{
    bian[++cnt].nxt=hd[x];
    bian[cnt].to=y;
    bian[cnt].val=z;
    hd[x]=cnt;
}
void dfs(int x)
{
    cout<<" now "<<x<<endl;
    vis[x]=1;

    for(int i=1;i<=k;i++)
      f[x][x][i]=0;//build one
    ll dis=0;
    for(int i=x;i!=0;i=fa[i])// not
    {
        dis+=disf[i];
        //if(x==3) cout<<fa[i]<<" "<<dis<<endl;
        f[x][fa[i]][0]=dis*w[x];
        f[x][fa[i]][1]=0;
    }

    for(int i=hd[x];i;i=bian[i].nxt)
    {
        int y=bian[i].to;
        if(!vis[y])
        {
            dfs(y);
            ll g[N][K];
            for(int o=0;o<N;o++)
             for(int u=0;u<K;u++)
              g[o][u]=inf;
            for(int p=1;p<=k;p++)//build one
            {
                for(int q=0;q<=p;q++)
                {
                    g[x][p]=min(g[x][p],f[x][x][p-q]+f[y][x][q]);
                }
            }
            ll dis=0;
            for(int j=x;j!=0;j=fa[j])//not
            {
                dis+=disf[j];
                for(int p=0;p<=k;p++)
                {
                    for(int q=0;q<=p;q++)
                    {
                        g[fa[j]][p]=min(g[fa[j]][p],f[x][fa[j]][p-q]+f[y][fa[j]][q]);
                    }
                }
            }
            for(int j=x;j!=-1;j=fa[j])
            {
                for(int p=0;p<=k;p++)
                 f[x][j][p]=g[j][p];
            }
            if(x==2)
            {
                cout<<"222222"<<endl;
                for(int p=0;p<=n;p++)
                {
                    for(int q=0;q<=k;q++)
                     cout<<p<<" "<<q<<" : "<<f[x][p][q]<<endl; 
                }
                cout<<endl;
            }
        }
    }

}
int main()
{
    scanf("%d%d",&n,&k);
    k++;//warning!!!
    int x,y,z;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&w[i],&y,&z);
        fa[i]=y;disf[i]=z;
        cout<<i<<" "<<" y "<<y<<" "<<fa[i]<<endl;
        add(i,y,z);
        add(y,i,z);
    }
    for(int i=0;i<=n;i++)
     cout<<i<<" fa "<<fa[i]<<" disf "<<disf[i]<<endl;
    fa[0]=-1;
    for(int i=0;i<N;i++)
     for(int j=0;j<N;j++)
      for(int o=0;o<K;o++)
        f[i][j][o]=inf;
    dfs(0);
    for(int i=0;i<=n;i++)
    {
        cout<<i<<" : "<<endl;
        for(int j=0;j<=n;j++)
         for(int o=0;o<=k;o++)
         {
            cout<<" anc "<<j<<" build "<<o<<" -> "<<f[i][j][o]<<endl;
         }
    }

    printf("%d",f[0][0][k]);
    return 0;
}