9/5 二维费用背包+基环树+01变型背包

二维费用背包

int n,V,M,v[N],w[N],val[N],f[N][N];

void solve()
{
    cin>>n>>V>>M;
    for(int i=1;i>v[i]>>w[i]>>val[i];
    for(int i=1;i=v[i];j--)
        {
            for(int k=M;k>=w[i];k--)
                f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+val[i]);
        }
    }
    coutu;
        add(u,i); //一个人可被多个人讨厌
    }
    for(int i=1;iu>>v;
        u++,v++;
        add(u,v),add(v,u);
    }
    cin>>k;
    fd(1,1);
    double sum=ans*k;
    printf("%.1lf\n",sum);
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

另一个写法，大同小异：

void fd(int u,int pre)
{
    if(flag)
        return;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==pre) continue;
        if(vis[v])
        {
            flag=1;
            r1=u,r2=v;return;
        }
        fd(v,u);
    }
}
int dfs(int u,int pre,int rt)
{
    f[u][0]=0,f[u][1]=a[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==pre||v==rt) continue;
        dfs(v,u,rt);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
    return f[u][0];
}

P1417 烹调方案

化简公式，对食物进行排序。由于美味值会衰减，因此并非越靠后要好，所以要对所有f[1~t]进行枚举取最大值。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);iy.b*x.c;
}
void solve()
{
    cin>>t>>n;
    for(int i=1;i>e[i].a;
    for(int i=1;i>e[i].b;
    for(int i=1;i>e[i].c;
    sort(e+1,e+n+1,cmp);
    for(int i=1;i=e[i].c;j--)
            f[j]=max(f[j],f[j-e[i].c]+e[i].a-j*e[i].b);
    }
    for(int i=1;i