I - Crazy Shopping ZOJ - 3524

题意

在一个DAG图上有N个点，每个点有重量为v[i]的价值为w[i]的物品无限个，背包容量为W，起点为X。背有重量为K的物品走dis的路程，消耗k*dis的体力。求达到最大价值时消耗的最小体力是多少。

题解

明显是一个完全背包的问题，但是不能直接按顺序更新点。DAG图于是需要先拓扑排序，再进行完全背包的dp。dp的时候需要同时更新价值和体力。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int N,M,W,X,tot,v[maxn],w[maxn],du[maxn],topus[maxn],vis[maxn];
struct node
{
    int net,dis;
};
vector<node>e[maxn];
struct ans
{
    int val,power;
}dp[maxn][maxn * 2];
void topusort()
{
    queue<int>Q;
    for(int i = 1;i <= N;i++)
    {
        if(du[i] == 0)
            Q.push(i);
    }
    tot = 0;
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        topus[++tot] = u;
        for(int i = 0;i < e[u].size();i++)
        {
            int to = e[u][i].net;
            du[to]--;
            if(du[to] == 0)    Q.push(to);
        }
    }
}
void slove()
{
    for(int i = 0;i <= W;i++)                            
    {
        dp[X][i].power = 0;
        if(i >= v[X])    dp[X][i].val = max(dp[X][i].val,dp[X][i - v[X]].val + w[X]);
    }
    vis[X] = 1;
    for(int i = 1;i <= N;i++)
    {
        int u = topus[i];
        if(!vis[u])    continue;
        for(int j = 0;j < e[u].size();j++)
        {
            int to = e[u][j].net;
            int dis = e[u][j].dis;
            vis[to] = 1;
            for(int k = 0;k <= W;k++)
            {
                if(dp[u][k].val > dp[to][k].val)
                {
                    dp[to][k].val = dp[u][k].val;
                    dp[to][k].power = dp[u][k].power + dis * k;
                }
                else if(dp[u][k].val == dp[to][k].val)
                {
                    if(dp[to][k].power >= 0)    dp[to][k].power = min(dp[to][k].power,dp[u][k].power + dis * k);
                    else                        dp[to][k].power = dp[u][k].power + dis * k;
                }
            }
            for(int k = v[to];k <= W;k++)
            {
                if(dp[to][k].val < dp[to][k - v[to]].val + w[to])
                {
                    dp[to][k].val = dp[to][k - v[to]].val + w[to];
                    dp[to][k].power = dp[to][k - v[to]].power;
                }
                else if(dp[to][k].val == dp[to][k - v[to]].val + w[to] && dp[to][k].power > dp[to][k - v[to]].power)
                {
                    dp[to][k].power = dp[to][k - v[to]].power;
                }
            }
        }
    }
}
void init()
{
    for(int i = 0;i <= N;i++)
    {
        e[i].clear();
        du[i] = 0;
        vis[i] = 0;
        for(int j = 0;j <= W;j++)
        {
            dp[i][j].power = -1;
            dp[i][j].val = 0;
        }
    }
}
int main()
{
    while(scanf("%d %d %d %d",&N,&M,&W,&X) != EOF)
    {
        init();
        for(int i = 1; i <= N; i++)
            scanf("%d %d",&v[i],&w[i]);
        for(int i = 1; i <= M; i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            node x;
            x.net = b,x.dis = c;
            e[a].push_back(x);
            du[b]++;
        }
        topusort();
        slove();
        int ans1,ans2;
        ans1 = 0;
        ans2 = 1e9;
        for(int i = 1; i <= N; i++)
        {
            for(int j = 0; j <= W; j++)
            {
                if(dp[i][j].val > ans1)
                {
                    ans1 = dp[i][j].val;
                    ans2 = dp[i][j].power;
                }
                else if(dp[i][j].val == ans1 && dp[i][j].power < ans2)
                {
                    ans2 = dp[i][j].power;
                }
            }
        }
        printf("%d\n",ans2);
    }
    return 0;
}