http://codeforces.com/contest/741/problem/B
题意：有 n 个人，每个人有一个花费 w[i] 和价值 b[i]，给出 m 条边，代表第 i 和 j 个人是一个集合的，给出一个最大花费 w，如果一个集合的人不能同时选的话，那么只能选集合中的其中一个或者不选，问按照这样的规则选得的花费不超过 w 的最大价值是多少。
思路：一开始搞个带权并查集出来，后来还是蒙了。之后看原来是01背包，然而已经N久没见过背包了。。。先用并查集弄出集合，然后对每个集合中的元素进行01背包（选集合中的一个或者不选的情况），在集合弄完之后还要对整体进行01背包（选集合中的全部），这里用了下滚动数组。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
int dp[][];
int fa[];
int b[], w[];
vector<int> vec[]; int Find(int x) {
if(x == fa[x]) return x;
return fa[x] = Find(fa[x]);
} int main()
{
int n, m, x;
scanf("%d%d%d", &n, &m, &x);
for(int i = ; i <= n; i++) scanf("%d", w + i);
for(int i = ; i <= n; i++) scanf("%d", b + i);
for(int i = ; i <= n; i++) fa[i] = i;
for(int i = ; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
u = Find(u), v = Find(v);
if(u != v) fa[u] = v;
}
for(int i = ; i <= n; i++)
vec[Find(i)].push_back(i);
int now = ;
for(int i = ; i <= n; i++) {
now = !now;
int ww = , bb = ;
for(int j = ; j <= x; j++) dp[now][j] = dp[!now][j];
for(int j = ; j < vec[i].size(); j++) {
int id = vec[i][j];
int www = w[id], bbb = b[id];
ww += www, bb += bbb;
for(int j = www; j <= x; j++) { // 在当前集合选一个最优
dp[now][j] = max(dp[now][j], dp[!now][j-www] + bbb);
}
}
for(int j = ww; j <= x; j++) { // 如果全部能丢进去
dp[now][j] = max(dp[now][j], dp[!now][j-ww] + bb);
}
}
int ans = ;
for(int i = ; i <= x; i++) ans = max(ans, dp[now][i]);
printf("%d\n", ans);
return ;
}