Mr. Panda and Crystal HDU - 6007 最短路+完全背包

题目：题目链接

思路：不难看出，合成每个宝石需要消耗一定的魔力值，每个宝石有一定的收益，所以只要我们知道每个宝石合成的最小花费，该题就可以转化为一个背包容量为初始魔力值的完全背包问题，每个宝石的最小花费可以用dijkstra跑一遍最短路算出，路径长度用合成花费表示。

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #include <queue>

 using namespace std;

 const int maxn =  + ;

 int vol, n, m, INF;

 struct node {

     int c, w;

     vector<int> v;

     vector<vector<pair<int, int> > > vec;

     friend bool operator < (node a, node b) {

         return a.w > b.w;

     }

 }gem[maxn];

 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;

 bool vis[maxn];

 void init() {

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

         for(int j = ; j < gem[i].vec.size(); ++j)

             gem[i].vec[j].clear();

         gem[i].vec.clear();

         gem[i].v.clear();

     }

     while(!q.empty())

         q.pop();

     memset(vis, false, sizeof(vis));

 }

 bool get_sum(int id) {

     int sum, _min = INF;

     for(int i = ; i < gem[id].vec.size(); ++i) {

         sum = ;

         for(int j = ; j < gem[id].vec[i].size(); ++j) {

             sum += gem[gem[id].vec[i][j].first].c * gem[id].vec[i][j].second;

             if(sum > INF)

                 sum = INF;

         }

         _min = min(_min, sum);

     }

     if(_min < gem[id].c) {

         gem[id].c = _min;

         return true;

     }

     return false;

 }

 void dijkstra() {

     while(!q.empty()) {

         pair<int, int> P = q.top();

         q.pop();

         if(vis[P.second])

             continue;

         vis[P.second] = true;

         for(int i = ; i < gem[P.second].v.size(); ++i) {

             if(!vis[gem[P.second].v[i]] && get_sum(gem[P.second].v[i])) {

                 q.push(make_pair(gem[gem[P.second].v[i]].c, gem[P.second].v[i]));

             }

         }

     }

 }

 int dp[maxn];

 int main()

 {

     ios::sync_with_stdio();

     cin.tie();

     int T, t = ;

     cin >> T;

     while(T--) {

         cin >> vol >> n >> m;

         INF = vol + ;

         init();

         int flag;

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

             cin >> flag;

             if(flag)

                 cin >> gem[i].c >> gem[i].w;

             else {

                 cin >> gem[i].w;

                 gem[i].c = INF;

             }

         }

         int id, num, c, nu;

         vector<pair<int, int> > ope;

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

             cin >> id >> num;

             ope.clear();

             for(int j = ; j < num; ++j) {

                 cin >> c >> nu;

                 ope.push_back(make_pair(c, nu));

                 gem[c].v.push_back(id);

             }

             gem[id].vec.push_back(ope);

         }

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

             if(gem[i].c < INF)

                 q.push(make_pair(gem[i].c, i));

         dijkstra();

         memset(dp, , sizeof(dp));

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

             for(int v = ; v <= vol; ++v)

                 if(v >= gem[i].c)

                     dp[v] = max(dp[v], dp[v - gem[i].c] + gem[i].w);

         cout << "Case #" << ++t << ": " << dp[vol] << endl;

     }

     return ;

 }

巴特西

Mr. Panda and Crystal HDU - 6007 最短路+完全背包

最新文章

热门文章