【题目链接】 http://codeforces.com/problemset/problem/741/B

【题目大意】

  给出一张图,所有连通块构成分组,每个点有价值和代价,
  要么选择整个连通块,要么只能在连通块中选择一个,或者不选,为最大价值

【题解】

  首先我们用并查集求出连通块,然后对连通块进行分组背包即可。

【代码】

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int N=1010;
int dp[N],f[N],n,m,x,y,size,w[N],b[N];
vector<int> v[N];
int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}
int main(){
while(~scanf("%d%d%d",&n,&m,&size)){
rep(i,n)f[i]=i,v[i].clear();
rep(i,n)scanf("%d\n",&w[i]);
rep(i,n)scanf("%d\n",&b[i]);
rep(i,m){scanf("%d%d",&x,&y);f[sf(x)]=sf(y);}
rep(i,n)v[sf(i)].push_back(i);
memset(dp,0,sizeof(dp));
rep(i,n)if(sf(i)==i){
for(int j=size;j>=0;j--){
int W=0,B=0;
for(int k=0;k<v[i].size();k++){
W+=w[v[i][k]]; B+=b[v[i][k]];
if(j>=w[v[i][k]])dp[j]=max(dp[j],dp[j-w[v[i][k]]]+b[v[i][k]]);
}if(j>=W)dp[j]=max(dp[j],dp[j-W]+B);
}
}printf("%d\n",dp[size]);
}return 0;
}

最新文章

  1. 将表里的数据批量生成INSERT语句的存储过程 继续增强版
  2. zjuoj 3609 Modular Inverse
  3. 【题解】【字符串】【BFS】【Leetcode】Word Ladder
  4. css之伪类选择器:before :after(::before ::after)
  5. Java Swing 探索(一)LayoutManager
  6. PHP重构之函数上移
  7. iOS开发之17个常用代码整理
  8. Spring MVC之视图解析器
  9. Java Web(二) Servlet中response、request乱码问题解决
  10. 安卓onTextChanged参数解释及实现EditText字数监听 Editable使用
  11. Oracle sql function LISTAGG
  12. ubuntu安装python版本的opencv
  13. CDB与PDB之间的切换方法
  14. Failed to start Vsftpd ftp daemon错误
  15. javap的使用
  16. denyhosts、中文文档乱码、端口占用查询
  17. [学习笔记]区间dp
  18. ZMQ和MessagePack的简单使用(转)
  19. springboot学习入门之四---开发Web应用之Thymeleaf篇
  20. ChemDraw加键的两种方法

热门文章

  1. Vue 使用中的小技巧(山东数漫江湖)
  2. 阿里云服务器下安装配置 vsftpd —— 基于CentOS 6.3 【简洁版】
  3. 20151024_003_C#基础知识(File / FileStream / StreamReader/StreamWriter)
  4. sublime3 快捷键大全
  5. 8.0docker的客户端和守护进程
  6. Linux 入门记录:十六、Linux 多命令协作:管道及重定向
  7. python基础===继承
  8. iptables 操作
  9. 【数位dp入门】【HDU4734】F(x)
  10. 谈谈mybatis逆向工程中的Example类