搭配购买

并查集 01背包 T3 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

题目

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 $n$ 朵云，云朵被编号为 $1,2,\dots ,n$，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 $1$ 行包含三个整数 $n，m，w$，表示有 $n$ 朵云，$m$ 个搭配，Joe有 $w$ 的钱。

第 $2\sim n+1$行，每行两个整数 $c_i$，$d_i$ 表示 $i$ 朵云的价钱和价值。

第 $n+2\sim n+1+m$ 行，每行两个整数 $u_i$，$v_i$，表示买 $u_i$ 就必须买 $v_i$，同理，如果买 $v_i$ 就必须买 $u_i$。

输出格式

一行，表示可以获得的最大价值。

数据范围

$1\le n\le 10000$ $0\le m\le 5000$ $1\le w\le 10000$ $1\le ci\le 5000$ $1\le di\le 100$ $1\le ui,vi\le n$

输入样例

5  3  10
3  10
3  10
3  10
5  100
10  1
1  3
3  2
4  2

输出样例

1

思路

需要求代价不超过 w 的最大价值, 是01背包问题。但这里多了一个要求, 有的商品拿了一个需要拿一系列有关的。

可以先用并查集处理, 把相关的缩成一个点, 枚举时只考虑 $f[x]==x$ 的点即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e4 + 10;
int w[N], f[N], v[N], res[N];
 
int find(int u)
{
    if (u != f[u])
        f[u] = find(f[u]);
    return f[u];
}
 
void merge(int a, int b)
{
    int pa = find(a), pb = find(b);
    f[pb] = f[pa];
    v[pa] += v[pb];
    w[pa] += w[pb];
}
 
int main()
{
    int n, m, t;
    cin >> n >> t >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
        f[i] = i;
    }
 
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (pa != pb)
            merge(a, b);
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (f[i] != i)
            continue;
        for (int j = m; j >= v[i]; j--)
            res[j] = max(res[j], res[j - v[i]] + w[i]);
    }
    cout << res[m] << endl;
    return 0;
}