美橙建站十四年,免费域名申请教程,做灯箱片的设计网站,买服务器做网站主机Joe觉得云朵很美#xff0c;决定去山上的商店买一些云朵。 商店里有 n 朵云#xff0c;云朵被编号为 1,2,…,n#xff0c;并且每朵云都有一个价值。但是商店老板跟他说#xff0c;一些云朵要搭配来买才好#xff0c;所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有…Joe觉得云朵很美决定去山上的商店买一些云朵。 商店里有 n 朵云云朵被编号为 1,2,…,n并且每朵云都有一个价值。但是商店老板跟他说一些云朵要搭配来买才好所以买一朵云则与这朵云有搭配的云都要买。但是Joe的钱有限所以他希望买的价值越多越好。
输入格式 第 1 行包含三个整数 nmw表示有 n 朵云m 个搭配Joe有 w 的钱。 第 2∼n1 行每行两个整数 cidi 表示 i 朵云的价钱和价值。 第 n2∼n1m 行每行两个整数 uivi表示买 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
解析
搭配的都要买可以理解成将有关系的都放在一起相当一个物品要买一起买。
这样就可以转换成01背包问题每个物品只能购买一次在有限的钱的情况下让买的物品的价值尽可能的大。
#include bits/stdc.h
using namespace std;
#define int long long
const int N2e610;
int p[N];
int v[N],w[N];
int v1[N],w1[N];
int f[N];
bool vis[N];
int find(int x)
{if (x!p[x]) p[x]find(p[x]);return p[x];
}
signed main()
{int n,m,k;cinnmk;for (int i1;in;i) p[i]i;for (int i1;in;i) cinv[i]w[i];for (int i0;im;i){int a,b;cinab;int xfind(a),yfind(b);if (x!y){v[y] v[x];w[y] w[x];p[x]y;}}int cnt0;for (int i1;in;i){int xfind(i);if (!vis[x]){cnt;v1[cnt]v[x];w1[cnt]w[x];vis[x]1;}}for (int i1;icnt;i) //01背包最简化 //模板for (int jk;jv1[i];j--)f[j]max(f[j],f[j-v1[i]]w1[i]);coutf[k];return 0;
}//发现可以简化一下代码不需要开新的数组记录每个“新的物品”的价值和代价。#include bits/stdc.h
using namespace std;
#define int long long
const int N2e610;
int p[N];
int v[N],w[N];
int f[N];
int find(int x)
{if (x!p[x]) p[x]find(p[x]);return p[x];
}
signed main()
{int n,m,k;cinnmk;for (int i1;in;i) p[i]i;for (int i1;in;i) cinv[i]w[i];for (int i0;im;i){int a,b;cinab;int xfind(a),yfind(b);if (x!y){v[y] v[x];w[y] w[x];p[x]y;}}for (int i1;in;i) //01背包最简化 //模板if (p[i]i) //每个集合的根节点{for (int jk;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);}coutf[k];return 0;
}
