http://blog.csdn.net/woshi250hua/article/details/7824773
题目大意：从前有n座山，山里都有一座庙，庙里都有一个老和尚，老和尚专送纪念品，每个纪念品重量为cost[i]，价值为val[i]。n座山形成一张有m条边的有向图，某山道某某山都有距离dist[i]。主角xx从st点出发，背着个容量为M的背包，想要收集最多的价值。但是主角体弱多病要顾及身体，每次背着重量为wi从某山走到某某山就要耗费dist[i]*wi的能量。最后能价值最多时最少的能量耗费为多少？
写下我的理解吧
首先我们要找到所有从x出发的通路，这个通过拓扑排序和标记来做到。
然后在这些通路中找到价值最大的:
在每个点通过之前传递的dp信息，用多重背包找出当前点价值最大，价值相等时找出精力最小
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 1010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f struct node { int v,len; }cur; vector<node> mmap[705]; int n,m,w,x; int tw[705],tv[705],cnt[705]; int st[705],result[705],flag[705]; long long dp[705][2005],power[705][2005],ans,dist; void ptopo() { for(int i =1;i<=n;i++) pf("%d ",result[i]); blank; } void Debug_InPut() { for (int i = 1; i <= n; ++i) for (int j = 0; j <= w; ++j) pf("(%lld %lld)%c",dp[i][j],power[i][j],j==w?' ':' '); } void init() { ans = 0; 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 topo() { int i,j; int tot = -1,index=0; for(i=1;i<=n;i++) { if(cnt[i]==0) st[++tot] = i; //pf("%d ",st[tot]); } //blank; while(tot>=0) { int xx = st[tot--]; result[++index] = xx; int s = mmap[xx].size(); //pf("tot%d ",tot); for(j=0;j<s;j++) { cur = mmap[xx][j]; int y = cur.v; //pf("xx%d y%d ",xx,y); cnt[y]--; if(cnt[y]==0) { st[++tot] = y; //pf("tot%d ",tot); //pf("y%d ",y); } } } //ptopo(); } void solve() { int i,j,k; for(i=0;i<=w;i++) { power[x][i] = 0; if(i>=tw[x]) { dp[x][i] = max(dp[x][i],dp[x][i-tw[x]]+tv[x]); } if (dp[x][i] > ans) ans = dp[x][i],dist = 0; } flag[x] = 1; for(i=1;i<=n;i++) { int xx = result[i]; if(flag[xx]==0) continue; int s = mmap[xx].size(); for(j=0;j<s;j++) { cur = mmap[xx][j]; int tp = cur.v; flag[tp] = 1; for(k=0;k<=w;k++) { if(dp[tp][k] < dp[xx][k]) { dp[tp][k] = dp[xx][k]; power[tp][k] = power[xx][k] + cur.len*k; } else if(dp[tp][k] == dp[xx][k]) { if(power[tp][k] == -1) { power[tp][k] = power[xx][k]+cur.len * k; } else power[tp][k] = min(power[xx][k] + cur.len*k ,power[tp][k]); } } for (k = tw[tp]; k <= w; ++k) { //完全背包 if (dp[tp][k] < dp[tp][k-tw[tp]]+tv[tp]) { dp[tp][k] = dp[tp][k-tw[tp]] + tv[tp]; power[tp][k] = power[tp][k-tw[tp]]; } else if(dp[tp][k] == dp[tp][k-tw[tp]]+tv[tp]) power[tp][k] = min(power[tp][k],power[tp][k-tw[tp]]); } for (k = 0; k <= w; ++k) { //更新答案 if (dp[tp][k] > ans) ans = dp[tp][k],dist = power[tp][k]; else if (dp[tp][k] == ans) dist = min(dist,power[tp][k]); } //pf("cur %d: ",cur.v),Debug_InPut(); } } } int main() { int i,j; while(~sf("%d%d%d%d",&n,&m,&w,&x)) { init(); for(i=1;i<=n;i++) sf("%d%d",&tw[i],&tv[i]); for(i=0;i<m;i++) { int x,y,l; sf("%d%d%d",&x,&y,&l); cur.v = y; cur.len = l; cnt[y]++; mmap[x].pb(cur); } topo(); solve(); //pf("ans %lld %lld ",ans,dist); printf("%lld ",dist); } return 0; }