#include using namespace std; const int N = 10010; int n, m, sum; // 有 n 朵云,m 个搭配,Joe有 sum 的钱。 int v[N], w[N]; // 表示 i 朵云的价钱和价值 int p[N]; // 并查集数组 int f[N]; // 01背包数组 // 最简并查集 int find(int x) { if (p[x] != x) p[x] = find(p[x]); // 路径压缩 return p[x]; } int main() { scanf("%d %d %d", &n, &m, &sum); // 初始化并查集 for (int i = 1; i <= n; i++) p[i] = i; // 读入每个云朵的价钱(体积)和价值 for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]); while (m--) { int a, b; cin >> a >> b; // 两种云朵需要一起买 int pa = find(a), pb = find(b); if (pa != pb) { // 集合有两个属性:总价钱、总价值,都记录到root节点上 v[pb] += v[pa]; w[pb] += w[pa]; p[pa] = pb; } } // 01背包 // 注意:这里不能认为一维的能AC,二维的替代写法就一定能AC // 这是因为这里的判断p[i]==i,导致i不一定是连续的, // 所以f[i][j]=f[i-1][j]这句话就不一定对 // 所以,看来终极版本的01背包一维解法还是有一定价值的。 for (int i = 1; i <= n; i++) if (p[i] == i) // 只关心集合代表元素,选择一组 for (int j = sum; j >= v[i]; j--) // 体积由大到小,倒序,01背包 f[j] = max(f[j], f[j - v[i]] + w[i]); // 输出最大容量下获取到的价值 printf("%d\n", f[sum]); return 0; }