ZOJ-3524 拓扑排序+完全背包（好题）

题意：在一个DAG上，主角初始有W钱起点在s点，每个点有一个代价wi和价值vi，主角从起点走到某一点不能回头走，一路上可以买东西（一个点的东西可以买无限次），且体力消耗为身上负重*路径长度。主角可以在任意一点停止旅程，问在获得最大价值情况下体力消耗最小。

解法：第一次遇到这类型的题，看大佬题解，这里说下自己的理解。首先主角在DAG上走且不能回头，那么比较明显让我们想到按拓扑排序顺序进行dp，这是正确的但是代码实现可能不那么容易想：我们首先对DAG进行拓扑排序求出它的拓扑序V，按照拓扑序进行完全背包的DP，这里要注意一点就是因为主角是有起点的，所以有的地方是根本到达不到的，我们可以用个vis数组来代表主角能到达的点，能动到达的点才能DP。DP思路是：设计状态dp[x][j]为走到x点，容量为j的最大价值，同时tp[x][j]为最大价值为dp[x][j]时候的最小体力消耗，那么我们到一个新点，我们先对这个的的物品做完全背包，然后用这个点x去更新x的下一步y的状态（这也是拓扑序DP的核心）。DP的同时更新答案即可。

这里提出一个问题就是为什么在两个限制下要求的答案dp状态不用设计成三维的呢？设计成两位状态能保证是在容量限制下最大价值且在最大价值下的最小消耗吗？这个问题蒟蒻一开始想不通，这是因为答案只要最好的。当然也可以把状态设计成例如dp[x][j][k]代表到x点容量为j价值为k的最小体力消耗，但是注意到因为题目要求的是最大价值下的最小消耗，所以这个状态的除了dp[x][j][Maxv](Maxv是x点容量j的最大价值)是有用的，其他的都是没用的dp[x][j][val] (val<Maxv)。因为此时容量已经确定，那么以后的状态在这些状态中容量相等的肯定选价值最大的，其他价值小的不会对后面结果造成任何影响。

除此以为这道题还有一些细节，不懂的建议看代码理解：

#include<bits/stdc++.h>

using namespace std;

const int N=+;

const int M=6e4+;

int n,m,W,s,Maxv,Mint,deg[N],w[N],v[N];

vector<int> V;

int cnt=,head[N],nxt[M],to[M],len[M];

void add_edge(int x,int y,int z) {

    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;

}

queue<int> q;

void toposort() {

    for (int i=;i<=n;i++) if (deg[i]==) q.push(i);

    while (!q.empty()) {

        int x=q.front(); q.pop();

        V.push_back(x);

        for (int i=head[x];i;i=nxt[i]) {

            int y=to[i];

            if (--deg[y]==) q.push(y);

        }

    }

}

bool vis[N];

int dp[N][],tp[N][];

void solve() {

    memset(dp,,sizeof(dp));

    memset(tp,0x3f,sizeof(tp));

    memset(vis,,sizeof(vis)); vis[s]=;

    dp[s][]=; tp[s][]=;

    for (int i=;i<V.size();i++) {

        if (!vis[V[i]]) continue;

        int x=V[i];

        for (int j=w[x];j<=W;j++)

            if (dp[x][j-w[x]]+v[x]>dp[x][j]) dp[x][j]=dp[x][j-w[x]]+v[x],tp[x][j]=tp[x][j-w[x]];

            else if (dp[x][j-w[x]]+v[x]==dp[x][j]) tp[x][j]=min(tp[x][j],tp[x][j-w[x]]);

        for (int j=head[x];j;j=nxt[j]) {

            int y=to[j];

            vis[y]=;

            for (int k=;k<=W;k++)

                if (dp[x][k]>dp[y][k]) {

                    dp[y][k]=dp[x][k];

                    tp[y][k]=tp[x][k]+len[j]*k;

                } else if (dp[y][k]==dp[x][k]) {

                    int tmp=tp[x][k]+len[j]*k;

                    tp[y][k]=min(tp[y][k],tmp);

                }

        }

        for (int j=;j<=W;j++)

            if (dp[x][j]>Maxv || dp[x][j]==Maxv && tp[x][j]<Mint) {

                Maxv=dp[x][j]; Mint=tp[x][j];

            }

    }

}

int main()

{

    while (scanf("%d%d%d%d",&n,&m,&W,&s)==) {

        for (int i=;i<=n;i++) scanf("%d%d",&w[i],&v[i]);

        memset(deg,,sizeof(deg));

        cnt=; memset(head,,sizeof(head));

        for (int i=;i<=m;i++) {

            int x,y,z; scanf("%d%d%d",&x,&y,&z);

            add_edge(x,y,z); deg[y]++;

        }

        V.clear(); toposort();

        Maxv=; Mint=0x3f3f3f3f;

        solve();

        printf("%d\n",Mint);

    }

    return ;

}

巴特西

ZOJ-3524 拓扑排序+完全背包（好题）

最新文章

热门文章