洛谷 P1455 搭配购买

题目描述明天就是母亲节了电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢听说在某个网站上有卖云朵的小朋友们决定一同前往去看看这种神奇的商品这个店里有 n 朵云云朵已经被老板编号为 1,2,3,...,n并且每朵云都有一个价值但是商店的老板是个很奇怪的人他会告诉你一些云朵要搭配起来买才卖也就是说买一朵云则与这朵云有搭配的云都要买电脑组的你觉得这礼物实在是太新奇了但是你的钱是有限的所以你肯定是想用现有的钱买到尽量多价值的云。输入格式第一行输入三个整数n,m,w表示有 n 朵云m 个搭配和你现有的钱的数目。第二行至 n1 行每行有两个整数 ci​,di​表示第 i 朵云的价钱和价值。第 n2 至 n1m 行 每行有两个整数 ui​,vi​。表示买第 ui​ 朵云就必须买第 vi​ 朵云,同理如果买第 vi​ 朵就必须买第 ui​ 朵。输出格式一行表示可以获得的最大价值。输入输出样例输入 #1复制5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2输出 #1复制1说明/提示对于 30% 的数据满足 1≤n≤100对于 50% 的数据满足 1≤n,w,ci​,di​≤1031≤m≤100对于 100% 的数据满足 1≤n,w,ci​,di​≤1040≤m≤5×103。#includebits/stdc.h using namespace std; const int N1e410; int c[N],d[N]; bool st[N]; int cc[N],dd[N]; vectorint aa[N]; int cnt; int f[N]; void dfs(int a) { st[a]true; cc[cnt]c[a]; dd[cnt]d[a]; for(auto x:aa[a]){ if(!st[x]){ dfs(x); } } } int main() { int n,m,w; cinnmw; for(int i1;in;i) { cinc[i]d[i]; } for(int j1;jm;j) { int a,b; cinab; aa[a].push_back(b); aa[b].push_back(a); } for(int i1;in;i) { if(!st[i]) { cnt; dfs(i); } } for(int i1;icnt;i) { for(int jw;jcc[i];j--) { f[j]max(f[j],f[j-cc[i]]dd[i]); } } coutf[w]endl; return 0; }