题目原文
Joe觉得云朵很美,决定去山上的商店买一些云朵。
商店里有 n 朵云,云朵被编号为 1,2,…,n,并且每朵云都有一个价值。
但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限,所以他希望买的价值越多越好。
输入格式
第 1 行包含三个整数 n,m,w,表示有 n 朵云,m 个搭配,Joe有 w 的钱。
第 2∼n+1行,每行两个整数 ci,di 表示 i 朵云的价钱和价值。
第 n+2∼n+1+m 行,每行两个整数 ui,vi,表示买 ui 就必须买 vi,同理,如果买 vi 就必须买 ui。
输出格式
一行,表示可以获得的最大价值。
数据范围
1≤n≤10000 ,
0≤m≤5000,
1≤w≤10000,
1≤ci≤5000,
1≤di≤100,
1≤ui,vi≤n
输入样例:
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
输出样例:
1
思路分析
稍微理解一下题意就会发现是dp问题,重点是如何处理题目中加粗部分,即如何将两个物品捆绑起来。其实这种说法是不准确的,这也是造成了我思路错误的原因。最开始的思路就是简单的相加,写完之后发现样例过不了,debug时发现了问题。
正确的思路是并查集+01背包,最基础的并查集就可以实现,然后再用一维数组的01背包计算就行。(虽然写完后又wa了)(在线卑微.jpg)
代码实现
感觉好笨拙的代码
#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10 ; int n,m,w; int c1[N],d1[N]; int c[N],d[N]; int root[N]; int f[N]; int find(int x){ if(root[x] == x) return x; else return find(root[x]); } void uunion(int a,int b){ int x = find(a) , y = find(b); root[y] = x; //c[x] += c[y]; //d[x] += d[y]; } int main(){ cin>>n>>m>>w; for(int i = 1; i <= n; i++) cin>>c1[i]>>d1[i],root[i] = i; while(m--){ int x,y; cin>>x>>y; uunion(x,y); } for(int i = 1; i <= n; i++){ int u = find(i); c[u] += c1[i],d[u] += d1[i]; } // for(int i = 1; i <= n; i++) // cout<<c[i]<<" "<<d[i]<<endl; for(int i = 1; i <= n; i++){ //if(!c[i] || !d[i]) continue; if(root[i] == i){ for(int j = w; j >= c[i]; j--) f[j] = max(f[j] , f[j-c[i]]+d[i]); } } cout<<f[w]<<endl; return 0; }
好吧这是个水题。
要补补并查集了(告辞)