Codeforces#383D. Arpa's weak amphitheater and Mehrdad's valuable Hoses(并查集+分组背包）

D. Arpa's weak amphitheater and Mehrdad's valuable Hoses time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Just to remind, girls in Arpa's land are really nice.

Mehrdad wants to invite some Hoses to the palace for a dancing party. Each Hos has some weight wi and some beauty bi. Also each Hos may have some friends. Hoses are divided in some friendship groups. Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, ..., ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.

Arpa allowed to use the amphitheater of palace to Mehrdad for this party. Arpa's amphitheater can hold at most w weight on it.

Mehrdad is so greedy that he wants to invite some Hoses such that sum of their weights is not greater than w and sum of their beauties is as large as possible. Along with that, from each friendship group he can either invite all Hoses, or no more than one. Otherwise, some Hoses will be hurt. Find for Mehrdad the maximum possible total beauty of Hoses he can invite so that no one gets hurt and the total weight doesn't exceed w.

Input

The first line contains integers n, m and w (1  ≤  n  ≤  1000, , 1 ≤ w ≤ 1000) — the number of Hoses, the number of pair of friends and the maximum total weight of those who are invited.

The second line contains n integers w1, w2, ..., wn (1 ≤ wi ≤ 1000) — the weights of the Hoses.

The third line contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 106) — the beauties of the Hoses.

The next m lines contain pairs of friends, the i-th of them contains two integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi), meaning that Hoses xiand yi are friends. Note that friendship is bidirectional. All pairs (xi, yi) are distinct.

Output

Print the maximum possible total beauty of Hoses Mehrdad can invite so that no one gets hurt and the total weight doesn't exceed w.

Examples input 3 1 5 3 2 5 2 4 2 1 2 output 6 input 4 2 11 2 4 6 6 6 4 2 1 1 2 2 3 output 7 Note

In the first sample there are two friendship groups: Hoses {1, 2} and Hos {3}. The best way is to choose all of Hoses in the first group, sum of their weights is equal to 5 and sum of their beauty is 6.

In the second sample there are two friendship groups: Hoses {1, 2, 3} and Hos {4}. Mehrdad can't invite all the Hoses from the first group because their total weight is 12 > 11, thus the best way is to choose the first Hos from the first group and the only one from the second group. The total weight will be 8, and the total beauty will be 7.

题意 ： 对于给定 n 个模特，每个模特有一个体重 wi ,和魅力值 bi ，同时给这些模特一些朋友关系，如果 x 和 y 是朋友，那么 x 的朋友和 y 的朋友也是朋友。那么这样可以将这些模特根据朋友圈子分类。现在有个人想开一个party，他希望在模特的体重之和不超过 k 的情况下使得魅力值最大，问，这个最大的魅力值是多少。同时需要注意的是，对于一个朋友圈子的模特，你有两种选择，一种是邀请整个圈子里的模特，或者只邀请这个圈子里的不超过1个模特。

思路

如果熟悉背包问题的人可能比较容易反应过来这是个背包问题的变形。但是即使熟悉背包问题，也会觉得“小团体”要么全拿要么只能拿一个的规则十分棘手。  考虑将有  x  个人的小团体看做一个“联合实体”，也就是一个人。那么我们可以将小团体看成一个集合，其中有  x+1  个元素，其中包括  x  个人和我们创造的“联合实体”。显然对这个集合，我们要么不取这个集合中的元素，要么只取集合中的一个元素。我们可以处理出所有的集合（通过用并查集合并出“联合实体”）。  处理出这些集合又该怎么办呢？熟悉分组背包的人会发现这是一个分组背包问题。每个集合是分组背包中的一个物品组，用一组的物品反复利用上一组的信息更新  DP  二维表中的一行然后每组新开一行即可。

#include<bits/stdc++.h> using namespace std; const int maxn = 2005; int n, m, k, wei[maxn], bea[maxn], Wei[maxn], Bea[maxn], fa[maxn]; bool vis[maxn]; void init() { for(int i = 1; i <= n; i++) { fa[i] = i; Wei[i] = wei[i]; Bea[i]= bea[i]; } } int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); } void Union(int p, int q) { int f1 = getf(p); int f2 = getf(q); if(f1 == f2) return ; Wei[f2] += Wei[f1]; Bea[f2] += Bea[f1]; fa[f1] = f2; } int main() { while(cin >> n >> m >> k) { vector<int> group[maxn]; for(int i = 1; i <= n; i++) scanf("%d", &wei[i]); for(int i = 1; i <= n; i++) scanf("%d", &bea[i]); init(); while(m--) { int u, v; scanf("%d%d", &u, &v); Union(u, v); } for(int i = 1; i <= n; i++) { int f = getf(i); group[f].push_back(i); } int cnt = n; memset(vis, false, sizeof(vis)); for(int i = 1; i <= n; i++) { int f = getf(i); if(vis[f] == false) { group[f].push_back(++cnt); wei[cnt] = Wei[f]; bea[cnt] = Bea[f]; vis[f] = true; } } int dp1[maxn], dp2[maxn]; memset(dp1, 0, sizeof(dp1)); for(int i = 1; i <= n; i++) { memset(dp2, 0, sizeof(dp2)); for(int u : group[i]) { for(int j = k; j >= wei[u]; j--) { dp2[j] = max(dp2[j], dp1[j-wei[u]] + bea[u]); } } /*for(int u = 0; u < group[i].size(); u++) { for(int j = k; j >= wei[group[i][u]]; j--) { dp2[j] = max(dp2[j], dp1[j-wei[group[i][u]]] + bea[group[i][u]]); } }*/ for(int j = 0; j <= k; j++) dp1[j] = max(dp1[j], dp2[j]); } int ans = 0; for(int i = 1; i <= k; i++) ans = max(ans, dp1[i]); cout << ans << endl; } return 0; }