Vijos P1250 - 最勇敢的机器人
传送门
思路
用并查集，然后分组背包。
背包九讲造福人类。
分组背包和一般的背包差不多，就是把一组作为一个点考虑。
在如何把它们集中到一组想了很久，后来还是暴力了。先把它们都分好，然后扫描一遍根节点，把相同根节点的都存到一个数组里，然后遍历一遍数组。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <cctype>
#define MP(a, b) make_pair(a, b)
using namespace std;
const int MAXN = 1000 + 5;
const int INF = 0x3f3f3f3f;
struct EQP
{
int val, w;
}eqp[MAXN];
vector<int> ve[MAXN];
int dp[MAXN][10000], pa[MAXN];
int Find(int x)
{
return pa[x] == x ? x : pa[x] = Find(pa[x]);
}
int main()
{
//freopen("input.txt", "r", stdin);
int n, wMax, k, i, j;
scanf("%d%d%d", &n, &wMax, &k);
for (i = 1; i <= n; i++)
scanf("%d%d", &eqp[i].val, &eqp[i].w);
for (i = 1; i <= n; i++)
pa[i] = i;
for (i = 0; i < k; i++)
{
int a, b;
scanf("%d%d", &a, &b);
int x = Find(a), y = Find(b);
if (x != y)
pa[x] = y;
}
for (i = 1; i <= n; i++)
{
int x = Find(i);
ve[x].push_back(i);
}
int cnt = 0;
for (i = 1; i <= n; i++)
{
if (!ve[i].empty())
{
cnt++;
for (j = 0; j <= wMax; j++)
{
dp[cnt][j] = dp[cnt - 1][j];
for (int k = 0; k < ve[i].size(); k++)
if (j >= eqp[ve[i][k]].w)
dp[cnt][j] = max(dp[cnt][j], dp[cnt - 1][j - eqp[ve[i][k]].w] + eqp[ve[i][k]].val);
}
}
}
printf("%d\n", dp[cnt][wMax]);
return 0;
}