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]+cur.len * 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原創，但可以轉載，因為我們是兄弟。