Mr. Panda and Crystal(最短路+完全背包)

http://codeforces.com/gym/101206/attachments

题意:

T组输入，每组给出m,n,k，m为能量总数，n为水晶种类数，k为合成方案数。有的水晶可以用能量制造，有的水晶不行，有的水晶可以通过其他水晶合成。每种水晶都有固定的价格。给出部分水晶的造价，所有水晶的价格和k个合成方案，问卖水晶最大能获得的钱数

思路：

可以将合成操作理解为最短路中的松弛操作，套bellman_ford的方法，每次遍历所有合成方案一次，若没有一个水晶造价被松弛，则跳出循环，所有造价均已达到最小

之后套用完全背包即可(每种水晶可以使用无限次，能量有限)

#include <bits//stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=205;

ll w[maxn],p[maxn];

ll obj[maxn],num[maxn],use[maxn][maxn],cost[maxn][maxn];

ll dp[maxn];

int T,m,n,k;

void bellman_ford(){

    while(1){

        int flag=0;

        for(int i=1;i<=k;i++){

            ll cos=0;

            for(int j=1;j<=num[i];j++){

                if(w[use[i][j]]==-1){

                    cos=-1;break;

                }

                cos+=w[use[i][j]]*cost[i][j];

            }

            if(cos!=-1){

                if(cos<w[obj[i]]||w[obj[i]]==-1){

                    w[obj[i]]=cos;

                    flag=1;

                }

            }

        }

        if(!flag)break;

    }

}

void init(){

    for(int i=1;i<=n;i++){

        w[i]=-1;

    }

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

        dp[i]=0;

}

int main(){

    cin>>T;

    for(int kase=1;kase<=T;kase++){

        scanf("%d%d%d",&m,&n,&k);

        init();

        for(int i=1;i<=n;i++){

            int type;

            scanf("%d",&type);

            if(type)

                scanf("%lld%lld",&w[i],&p[i]);

            else

                scanf("%lld",&p[i]);

        }

        for(int i=1;i<=k;i++){

            scanf("%lld%lld",&obj[i],&num[i]);

            for(int j=1;j<=num[i];j++){

                scanf("%lld%lld",&use[i][j],&cost[i][j]);

            }

        }

        bellman_ford();

        for(int i=1;i<=n;i++){

            if(w[i]==-1)continue;

            for(int j=w[i];j<=m;j++){

                dp[j]=max(dp[j],dp[j-w[i]]+p[i]);

            }

        }

        printf("Case #%d: %lld\n",kase,dp[m]);

    }

}

/*

2

100 3 2

0 20

1 15 10

1 2 1

1 2 2 1 3 1

2 1 3 2

100 3 2

1 3 1

1 4 1

0 10

3 1 1 3

3 1 2 2

*/