#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
typedef long long ll;
using namespace std;
ll P[1002],W[1002],fz[1002];//W价值 P表重量
struct fff{
ll vi[1002];
ll pi[1002];
ll num;
bool book;
}ww[1002];
ll f[1002][1002];
ll gets(ll x){
if(fz[x]==x) return x;
else fz[x]=gets(fz[x]);
}
int main(){
// freopen("robots.in","r",stdin);
// freopen("robots.out","w",stdout);
ll n,m,k;
cin>>n>>m>>k;
int i;
for(i=1;i<=n;i++){
cin>>W[i]>>P[i];
fz[i]=i;
ww[i].num=0;
ww[i].book=false;
}
for(i=1;i<=k;i++){
ll x,y;
cin>>x>>y;
ll t1=gets(x);
ll t2=gets(y);
if(t1!=t2) fz[t2]=t1;
}
for(i=1;i<=n;i++)
{
if(fz[i]==i){
ww[i].pi[ww[i].num]=P[i];
ww[i].vi[ww[i].num]=W[i];
ww[i].num++;
ww[i].book=true;
}
else{
ll t=gets(i);
ww[t].pi[ww[t].num]=P[i];
ww[t].vi[ww[t].num]=W[i];
ww[t].num++;
ww[t].book=true;
}
}
int tol=0;
for(i=1;i<=n;i++){
if(ww[i].book==true){
tol++;
for(int j=0;j<ww[i].num;j++){
for(int t=ww[i].pi[j];t<=m;t++){
f[tol][t]=max(f[tol][t],f[tol-1][t-ww[i].pi[j]]+ww[i].vi[j]);
f[tol][t]=max(f[tol][t],f[tol-1][t]);
}
}
}
}
cout<<f[tol][m];
return 0;
}
1 条评论
-
LiuWeiMing1997 LV 8 @ 2016-12-21 23:38:38
分组背包问题
并查集后进行dp，记得判断枚举的背包容量v要大于当前物品的重量，才能进行转移，否则会越界。
```c++
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1000 + 20;
int fa[maxn];
int dp[maxn * 10 + 20];
int tofind(int u) {
if (fa[u] == u) return fa[u];
else return fa[u] = tofind(fa[u]);
}
void tomerge(int x, int y) {
x = tofind(x);
y = tofind(y);
fa[y] = x;
}
vector<int>gg[maxn];
int w[maxn];
int val[maxn];
void work() {
int n, tot, k;
cin >> n >> tot >> k;
for (int i = 1; i <= n; ++i) {
cin >> val[i] >> w[i];
fa[i] = i;
}
for (int i = 1; i <= k; ++i) {
int a, b;
cin >> a >> b;
tomerge(a, b);
}
for (int i = 1; i <= n; ++i) {
gg[tofind(i)].push_back(i);
}
for (int i = 1; i <= n; ++i) {
if (gg[i].size() == 0) continue;
for (int j = tot; j >= 1; --j) {
for (int h = 0; h < gg[i].size(); ++h) {
if (j >= w[gg[i][h]])
dp[j] = max(dp[j], dp[j - w[gg[i][h]]] + val[gg[i][h]]);
}
}
}
cout << dp[tot] << endl;
}int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return 0;
}
```
- 1
