HDU 6007 Mr. Panda and Crystal（dijkstra变形+完全背包）

Mr. Panda and Crystal

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 979    Accepted Submission(s): 322

 

Problem Description

Long long time ago, there is a magic continent far far away.
There are N types of magic crystals that contain ancient magic powers. Each of the type of magic crystal has its own price for one piece in the market. As the most powerful magician, Mr. Panda could synthesize some types of crystals by collecting some amount of other types of crystals. He could also create some types of crystals by using some number of his magic powers.
Now, Mr Panda can create any number of crystals as he wish by using no more than M magic powers. He want to know the maximum amount of money he can make by sell all the crytals he creates and synthesizes.

 

 

Input

The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with 3 positive intergers, M, N and K represent the amount of magic powers Mr. Panda had, the number of crystal types on the magic continent and the number of crystal synthesis equations.
Then N lines follows, each of them starts with one 0 or 1 which indicates whehter Mr. Panda could create this type of crystal.
If the ith line starts with 0, which means Mr. Panda couldn’t create crystal type i. Then there is one integer pi in this line which is the price for each piece of crystal type i.
If the ith line starts with 1, which means Mr. Panda could create crystal type i. Then there are two positive integers ci and pi in this line, the first is the amout of magic power cost when creates one piece of crystal type i, and the second is is the price for each piece of crystal type i.
The following K lines each start with two interger xi and yi , which means for synthesizing one piece of crystal type xi , yi rules should be satisfied. Then there are yipair of positive intergers uj and vj means for one piece of xthi type cristal, we have to collect vi piece of crystal type ui. Only when all the rules of ui and vi are satisfied, Mr. Panda could synthesize one piece xthi type cristal.

 

 

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum amout of money Mr. Panda could make.

limits

∙1≤T≤100.
∙1≤M≤10000.
∙1≤N≤200.
∙1≤K≤200.
∙1≤xi,uj≤N.
∙foreachcrystalsynthesisequation,allujaredifferent.
∙1≤vj≤100.
∙1≤ci,pi≤10000.

 

 

Sample Input

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

 

 

Sample Output

Case #1: 330 Case #2: 121

题意：

给你n(n<=1e4),m(m<=2e2),k(k<=2e2)。你有n个魔法值。

接下来m行给出m种魔法石，每行格式为 id  如果id为0则为  id x 表示这个魔法石不可以合成，x即为卖出的价格。

如果id为1，则为 id x y，表示可以用x的魔法值合成这块魔法石，卖出可以得到y元。

接下来k行，给出k种合成方法。

每一行格式为  id x  表示第id种魔法石可以由x种其他魔法石合成。再给你2*x个数，每一对数<y,z>表示需要z块第y种魔法石。

问你n个魔法值最多可以赚多少钱。

题解：

很容易想到当每一种魔法石的合成最小消耗魔法值确定时，就是一个容量为n的完全背包。

但是最关键的是怎么求每一种魔法石的合成的最小消耗。

于是可以想到，利用dijkstra算法求最短路的思想，每一种魔法石向包含他的合成方案编号建边，将距离改为合成该方案的魔法石所消耗的总魔力值。如果对dijk算法非常熟练的话，那么这道题就很简单了。注意无法合成的魔法石重量置为n+1，否则可能会RE。

主要是还是要读懂题目。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 100000000000000000LL
using namespace std;
const int maxn=10010;
int n,m,k;
struct node
{
    int id;
    int dis;
    node(int x=0,int y=0){id=x;dis=y;}
    bool operator<(node aa)
    const{
        return dis>aa.dis;
    }
};
struct wupin
{
    int xh;
    int mon;
}a[maxn];
struct edge
{
    int he;
    vector<pair<int,int> >vc;
}p[210];
priority_queue<node>q;
int d[maxn];
bool vis[maxn];
vector<int>vv[maxn];
int getsum(edge &e)
{
    int sum=0;
    for(int i=0;i<e.vc.size();i++)
    {
        sum+=e.vc[i].second*d[e.vc[i].first];
    }
    return sum;
}
void dijk()
{
    while(!q.empty())
    {
        node no=q.top();q.pop();
        int u=no.id;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<vv[u].size();i++)
        {
            edge &e=p[vv[u][i]];
            int tmp=getsum(e);
            if(d[e.he]>tmp)
            {
                d[e.he]=tmp;
                q.push(node(e.he,d[e.he]));
            }
        }
    }
}
int dp[maxn];
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        while(!q.empty()) q.pop();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;i++)
        {
            vv[i].clear();
            int x,y;
            scanf("%d",&x);
            if(x==1)
            {
                scanf("%d%d",&x,&y);
                a[i].xh=x;
                a[i].mon=y;
                d[i]=x;
            }
            else
            {
                scanf("%d",&y);
                a[i].mon=y;
                a[i].xh=n+1;
                d[i]=n+1;
            }
        }
        for(int i=0;i<k;i++)
        {
            p[i].vc.clear();
            scanf("%d",&p[i].he);
            int x,y,z;
            scanf("%d",&x);
            for(int j=0;j<x;j++)
            {
                scanf("%d%d",&y,&z);
                p[i].vc.push_back(make_pair(y,z));
                vv[y].push_back(i);
            }
        }
        for(int i=1;i<=m;i++)
        if(d[i]<=n){
            q.push(node(i,d[i]));
        }
        dijk();
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++)
        for(int j=d[i];j<=n;j++)
        {
            dp[j]=max(dp[j],dp[j-d[i]]+a[i].mon);
        }
        printf("Case #%d: %d\n",cas++,dp[n]);
    }
    return 0;
}
/*
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
*/