题目描述
明天就是母亲节了,
电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢?
听说在某个网站上有卖云朵的,小朋友们决定一同前往去看看这种神奇的商品,
这个店里有 n朵云,云朵已经被老板编号为 1,2,3,…,n,
并且每朵云都有一个价值,但是商店的老板是个很奇怪的人,
他会告诉你一些云朵要搭配起来买才卖,也就是说买一朵云则与这朵云有搭配的云都要买,
电脑组的你觉得这礼物实在是太新奇了,但是你的钱是有限的,
所以你肯定是想用现有的钱买到尽量多价值的云。
输入格式
第一行输入三个整数,n,m,w,表示有 n朵云,m 个搭配和你现有的钱的数目。
第二行至 n+1 行,每行有两个整数,ci,di,表示第 i朵云的价钱和价值。
第 n+2至 n+1+m行 ,每行有两个整数ui,vi。表示买第ui朵云就必须买第v i朵云,同理,
如果买第vi朵就必须买第ui朵。
输出格式
一行,表示可以获得的最大价值。
对于 100% 的数据,满足 1≤n,w≤10^4 0≤m≤5×10^3。
样例
输入样例:
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
输出样例:
1
算法1
(并查集加01背包) $O(n^2)$
将有关系的物品合并成一个大物品,再用01背包即可
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010, M = N;
int newv[N], neww[N];
int f[N], p[N], v[N], w[N];
int n, m, k;
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void unite(int x, int y)
{
int px = find(x);
int py = find(y);
if (px < py)
{
v[px] += v[y];
w[px] += w[y];
p[py] = p[px];
}
else if (px > py)
{
v[py] += v[x];
w[py] += w[x];
p[px] = p[py];
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++)
p[i] = i;
while (m--)
{
int x, y;
scanf("%d%d", &x, &y);
unite(x, y);
}
int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (find(i) == i)
{
newv[++cnt] = v[i];
neww[cnt] = w[i];
}
}
for (int i = 1; i <= cnt; i++)
{
for (int j = k; j >= newv[i]; j--)
{
f[j] = max(f[j], f[j - newv[i]] + neww[i]);
}
}
printf("%d\n", f[k]);
return 0;
}