【题目信息】
【审题】
云和云之间有依赖关系,买一朵就要买与它相关的所有朵。
【分析】
1.使用并查集,路径压缩,将有关系的云缩成一件物品
2.01背包选出最优方案
【心路历程】
这道题嘛,我之前看过一模一样的,就这个,ybtoj1898骑上彩虹。
唉,退钱!
【代码】
#include <bits/stdc++.h> using namespace std; int n,m,w; const int maxn=100005; int c[maxn],d[maxn]; int f[maxn]; int a[maxn]; int u[maxn],v[maxn]; int dp[maxn]; int ans=0; struct New { int wei,pri,num; }q[maxn]; int find(int x) { if(f[x]==x) return x; return f[x]=find(f[x]); } void merge(int x,int y) { int k=find(x),w=find(y); if(k!=w ) { f[k]=w; } } int main() { scanf("%d %d %d",&n,&m,&w); for(int i=1;i<=n;i++) { scanf("%d %d",&c[i],&d[i]); } for(int i=1;i<=n;i++) { f[i]=i; } for(int i=1;i<=m;i++) { scanf("%d %d",&u[i],&v[i]); merge(u[i],v[i]); } for(int i=1;i<=n;i++) { if(find(i)!=i)//元素属于其他集合 { c[find(i)]+=c[i]; d[find(i)]+=d[i]; c[i]=d[i]=-1; } } for(int i=1;i<=n;i++) { if(c[i]>0&&d[i]>0) { ans++; q[ans].wei=d[i]; q[ans].pri=c[i]; q[ans].num=ans; } } /* for(int i=1;i<=ans;i++) { printf("%d %d %d\n",q[i].num,q[i].pri,q[i].wei); }*/ for(int i=1;i<=ans;i++) { for(int j=w;j>=q[i].pri;j--) { dp[j]=max(dp[j],dp[j-q[i].pri]+q[i].wei); } } printf("%d",dp[w]); return 0; }
江湖再见啦!