首页 > 代码库 > ZOJ 3524 Crazy Shopping DAG上的完全背包

ZOJ 3524 Crazy Shopping DAG上的完全背包

2024-07-16 04:20:46   220人阅读

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4439

题意：

n个点的有向无环图，边有长度，从一个点到另一点消耗背包重量与边长的乘积。每个点卖物品，价值v，重量w，数量无限，给定起点，和背包容量，可以在任意点停止，问最大化所获得价值的情况下需要消耗的最少能量。

分析：

前两天一拙计没想出来，先放着了，今天水了几次才过= =。f[i][j]表示在i点用j的容量所得最大价值，g[i][j]表示同样状态下获得最大价值所需最小能量，然后拓扑排序，转移即可。因为题是前两天读的，今天想了方程就写，忘记考虑图的连通性，如果不能由起点走到的点就不能用它的答案来更新解。

感想：

前两天卡住主要是突然想不清状态转移。实际上像这题，状态转移可以分开，即同时进行顺推和逆推，循环到i,j的状态时，既是求i,j的状态，也是将i,j的状态转移给所能到的点to,j。

 

 1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<queue> 5 using namespace std; 6  7 typedef pair<int, int> edge; 8 int n, m, w, x, st; 9 vector<edge> e[610];10 long long f[610][2100], g[610][2100];11 int c[610], v[610], bfn[610], in[610];12 bool reach[610];13 int main()14 {15     while(scanf("%d %d %d %d", &n, &m, &w, &x) != EOF)16     {17         for (int i = 1; i <= n; i++){18             scanf("%d %d", c+i, v+i); 19             e[i].clear();20         }21         memset(in, 0, sizeof(in));22         int xx, yy, ww;23         for (int i = 0; i < m; i++)24         {25             scanf("%d %d %d", &xx, &yy, &ww);26             e[xx].push_back(make_pair(yy, ww));27             in[yy] ++;28         }29         queue<int> q;30         for (int i = 1; i <= n; i++)31             if (in[i] == 0) q.push(i);32         int cnt = 0;33         while(!q.empty())34         {35             int u = q.front(); q.pop();36             bfn[++cnt] = u;37             if (u == x) st = cnt;38             for (int i = 0; i < e[u].size(); i++){39                 int v = e[u][i].first;40                 in[v] --;41                 if (!in[v]) q.push(v);42             }43         }44         memset(reach, false, sizeof(reach));45         reach[x] = true;46         long long ans = 1 << 30, maxv = 0;47         ans <<= 30;48         memset(f, 0, sizeof(f));49         for (int mark = st; mark <= n; mark++){50             int i = bfn[mark];51             if (!reach[i]) continue;52             for (int j = 0; j <= w; j++){53                 if (j >= c[i]){54                     long long tmp = f[i][j-c[i]] + v[i]; 55                     if (f[i][j] < tmp){56                         f[i][j] = tmp;57                         g[i][j] = g[i][j-c[i]];58                     }59                     else if (f[i][j] == tmp){60                         g[i][j] = min(g[i][j], g[i][j-c[i]]);61                     }62                 }63                 for (int t = 0; t < e[i].size(); t++){64                     int v = e[i][t].first, l = e[i][t].second;　　　　　　//v肯定还没遍历过65                     reach[v] = true;　　　　　　　　　　　　　　　　　　　　　//f[v][j]暂时表示v点j的容量全由之前点66                     if (f[i][j] > f[v][j]){　　　　　　　　　　　　　　　　　//消耗所能获得最大价值67                         f[v][j] = f[i][j];68                         g[v][j] = g[i][j] + l * j;69                     }70                     else if (f[i][j] == f[v][j]){71                         g[v][j] = min(g[v][j], g[i][j] + l * j);72                     }73                 }74                 if (f[i][j] > maxv){75                     maxv = f[i][j];76                     ans = g[i][j];77                 }78                 else if (f[i][j] == maxv) ans = min(ans, g[i][j]);79             }80         }81         printf("%lld\n", ans);82     }83     return 0;84 }

 


联系
我们