Zoj 3524 Crazy Shopping （DP_完全背包)
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4439
题目大意：从前有n座山，山里都有一座庙，庙里都有一个老和尚，老和尚专送纪念品，每个纪念品重量为cost[i]，价值为val[i]。n座山形成一张有m条边的有向图，某山道某某山都有距离dist[i]。主角xx从st点出发，背着个容量为M的背包，想要收集最多的价值。但是主角体弱多病要顾及身体，每次背着重量为wi从某山走到某某山就要耗费dist[i]*wi的能量。最后能价值最多时最少的能量耗费为多少？
解题思路：看上去像神题，但仔细分析就是一个拓扑排序+完全背包，不过细节着实有点蛋痛。我最开始是想先再每个点做一次完全背包，这样转移的时候直接转移就好了。但是这样似乎很难实现。
设dp[i][j]到达i点背包里装容量为j的最大价值，power[i][j]表示价值最大时的最小耗费。按上一段说的一开始就转移的话，那么dp[i][j]都会被更新，此时power[i][j]应该是0，因为不知道前面跑了几万几千里。但是这样并不靠谱，先不说从st能不能到i，就说能到达的时候，我们怎么得到一个和dp[i][j]一样的值，那么此时power应该更新为多少？还有dp[i][j]要怎么更新?
上面是我的一次失败的尝试，但对后面的分析也有帮助，我只要先进行拓扑排序，然后利用拓扑序向后转移，转移到下一个点就做一次完全背包，一个点可能从很多歌点转移来，优先更新dp[i][j]然后更新power[i][j],转移得到的dp[i][j]和power[i][j]都是从前序节点转移而来，如果.而每次转移的时候还必须对下一个节点进行标记，表示能否从st点而来。
具体的转移方程和完全背包很像，只是在价值一样的时候要依据power进行转移，实现见代码。
测试数据：
4 4 10 1
1 1
2 3
3 4
4 5
1 2 5
1 3 4
2 4 4
3 4 5
4 4 10 1
3 5
2 2
3 3
1 1
1 2 5
1 3 10
2 4 4
3 4 5
4 4 15 1
4 7
2 3
3 3
1 1
1 2 5
1 3 10
2 4 0
3 4 5
4 4 0 1
4 7
2 3
3 3
1 1
1 2 5
1 3 10
2 4 0
3 4 5
4 4 15 4
4 7
2 3
3 3
1 1
1 2 5
1 3 10
2 4 0
3 4 5
4 4 15 2
4 7
2 3
3 3
1 1
1 2 5
1 3 10
2 4 0
3 4 5
4 3 15 1
2 3
3 3
2 1
1 1
1 3 0
2 3 5
3 4 0
4 3 15 1
2 3
3 3
2 1
1 1
1 3 0
2 3 5
3 4 10
Output:
15 0
16 81
25 60
0 0
15 0
22 0
22 0
22 140
C艹代码：
#include <stdio.h>#include <string.h>#include <vector>#include <algorithm>using namespace std;#define MIN 700#define MAX 2100#define int64 long long#define min(a,b) ((a)<(b)?(a):(b))#define max(a,b) ((a)>(b)?(a):(b))struct node { int v,len;}cur;vector<node> mmap[MIN];int n,m,road,x,cost[MIN],val[MIN],flag[MIN];int st[MIN],top,cnt[MIN],real[MIN],Index;int64 dp[MIN][MAX],power[MIN][MAX],ans,dist;void Initial() { Index = 0; top = ans = dist = 0; memset(dp,0,sizeof(dp)); memset(cnt,0,sizeof(cnt)); memset(flag,0,sizeof(flag)); memset(power,-1,sizeof(power)); for (int i = 0; i <= n; ++i) mmap[i].clear();}void Debug_InPut() { for (int i = 1; i <= n; ++i) for (int j = 0; j <= m; ++j) printf("(%lld %lld)%c",dp[i][j],power[i][j],j==m?'\n':' ');}void ToooPooo() { for (int i = 1; i <= n; ++i) if (cnt[i] == 0) st[++top] = i; while (top != 0) { int v = st[top--]; real[++Index] = v; //printf("%d\n",v); int size = mmap[v].size(); for (int i = 0; i < size; ++i) { cur = mmap[v][i]; cnt[cur.v]--; if (cnt[cur.v] == 0) st[++top] = cur.v; } }}void Solve_AC() { int i,j,k,s,v,size,tp; for (j = 0; j <= m; ++j) {//相当于初始化 power[x][j] = 0; if (j >= cost[x]) dp[x][j] = max(dp[x][j],dp[x][j-cost[x]]+val[x]); if (dp[x][j] > ans) ans = dp[x][j],dist = 0; //printf("%d %lld ans%lld\n",j,dp[x][j],ans); } flag[x] = 1; for (i = 1; i <= n; ++i) { v = real[i]; if (flag[v] == 0) continue;//flag为0 ，表示不可达 size = mmap[v].size(); for (s = 0; s < size; ++s) { cur = mmap[v][s]; tp = cur.v,flag[tp] = 1;//可达,tp为下一个节点号 for (j = 0; j <= m; ++j) { if (dp[tp][j] < dp[v][j]) {//优先根据dp[tp][j]进行转移 dp[tp][j] = dp[v][j]; power[tp][j] = power[v][j] + cur.len * j; } else if (dp[tp][j] == dp[v][j]) {//当dp[tp][j]和dp[v][j]相等才根据power[i][j]转移 if (power[tp][j] == -1) //第一次到达tp点 power[tp][j] = power[v][j]; else power[tp][j] = min(power[tp][j],power[v][j] + cur.len * j); }//没有这个if就会出现后面的耗费比前面多，但实际获得的价值都一样 if (j && dp[tp][j] == dp[tp][j-1]) power[tp][j] = min(power[tp][j],power[tp][j-1]); } for (j = cost[tp]; j <= m; ++j) {//完全背包 if (dp[tp][j] < dp[tp][j-cost[tp]]+val[tp]) { dp[tp][j] = dp[tp][j-cost[tp]] + val[tp]; power[tp][j] = power[tp][j-cost[tp]]; } else if(dp[tp][j] == dp[tp][j-cost[tp]]+val[tp]) power[tp][j] = min(power[tp][j],power[tp][j-cost[tp]]); } for (j = 0; j <= m; ++j) {//更新答案 if (dp[tp][j] > ans) ans = dp[tp][j],dist = power[tp][j]; else if (dp[tp][j] == ans) dist = min(dist,power[tp][j]); } //printf("cur %d:\n",cur.v),Debug_InPut(); } }}int main(){ int i,j,k,a,b,c; while (~scanf("%d%d%d%d",&n,&road,&m,&x)) { Initial(); for (i = 1; i <= n; ++i) scanf("%d%d",&cost[i],&val[i]); for (i = 1; i <= road; ++i) { scanf("%d%d%d",&a,&b,&c); cnt[b]++; cur.v = b,cur.len = c; mmap[a].push_back(cur); } ToooPooo(); Solve_AC(); //printf("ans %lld %lld\n",ans,dist); printf("%lld\n",dist); }}本文ZeroClock原创，但可以转载，因为我们是兄弟。