正題

題目鏈接：
https://www.luogu.org/problemnew/show/P1455

---

大意

有n個商品，給出價值和價格。有m組搭配，如果買了其中一個就得買另一個，給出你擁有的錢，求能獲得的最大價值

---

解題思路

首先用并查集算出每個搭配的價格和價值，然后一遍01背包

---

代碼

#include<cstdio> #include<iostream> 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 fa=find(x),fb=find(y);if (fa<fb) {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 i=1;i<=n;i++){scanf("%d%d",&w[i],&c[i]);father[i]=i;}for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);unionn(x,y);}for (int i=1;i<=n;i++){if (father[i]==i){for (int j=t;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+c[i]);}}}//01背包printf("%d",f[t]); }

總結(jié)

以上是生活随笔為你收集整理的P1455-搭配购买【图论，并查集,dp，背包】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。