网站设计模板素材,江宁网站建设多少钱,网址检测,厦门网站建设平台正题
题目链接#xff1a; https://www.luogu.org/problemnew/show/P1455 大意
有n个商品#xff0c;给出价值和价格。有m组搭配#xff0c;如果买了其中一个就得买另一个#xff0c;给出你拥有的钱#xff0c;求能获得的最大价值 解题思路
首先用并查集算出每个搭配的…正题
题目链接 https://www.luogu.org/problemnew/show/P1455 大意
有n个商品给出价值和价格。有m组搭配如果买了其中一个就得买另一个给出你拥有的钱求能获得的最大价值 解题思路
首先用并查集算出每个搭配的价格和价值然后一遍01背包 代码
#includecstdio
#includeiostream
using namespace std;
int f[10001],father[10001],c[10001],w[10001];
int n,m,t,x,y;
int find(int x)
{if (x!father[x]) return father[x]find(father[x]);return father[x];
}
void unionn(int x,int y)
{int fafind(x),fbfind(y);if (fafb) {father[fb]fa;c[fa]c[fb];w[fa]w[fb];//计算价格}else {father[fa]fb;c[fb]c[fa];w[fb]w[fa];}
}
int main()
{scanf(%d%d%d,n,m,t);for (int i1;in;i){scanf(%d%d,w[i],c[i]);father[i]i;}for (int i1;im;i){scanf(%d%d,x,y);unionn(x,y);}for (int i1;in;i){if (father[i]i){for (int jt;jw[i];j--){f[j]max(f[j],f[j-w[i]]c[i]);}}}//01背包printf(%d,f[t]);
}
