太暴力了QAQ
题目描述
现在有n个人，每个人有责任度bi和影帝度wi，要从中钦定一个长老团
我们知道，一个好的长老团，他的责任度要越高越好，而为了防止_____，影帝度则不能超过给定的WW
此外，这些人之间有着奥妙穷穷的m条关系，具体来说就是m条xi和yi之间的关系
而如果x和y有关系y和z有关系，那么x和z也有关系，有关系的人分成一组的话，这些关系把n个候选人分成了若干组
为了保证关系的稳定，每一组中的人，要么全部被选入长老团，要么最多只能有一个人进入长老团
现在，请问这个长老团的责任度最高是多少
输入格式
输入3个整数n, m和w表示人数，关系数和影帝度上限
第二行包含n个数wi
第三行包含n个数bi
接下来m行每行两个整数xi,yi表示xi和yi之间有关系
输入样例
3 1 5
3 2 5
2 4 2
1 2
输出样例
6
样例解释
选1,21,2得到w=3+2=5, b=2+4=6
数据规模
对于20%的数据，1≤n≤18
对于100%的数据，1≤n≤1000, 1≤w≤1000, 1≤wi≤1000, 1≤bi≤106
关系是双向的，并且不会重复
这是一道背包问题，我们再考虑放入每组最优的同时也要尝试放入整组，由于人与人之间的关系，还是用个vector简单一些，注意范围中 bi>=1，所以不滚动直接dp是OK的（然而原本出的数据出现了偏差），而如果存在bi==0，那么我们只要把数组滚动就好了
别滚苟了。。。（滚苟的路过）
#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<vector> using namespace std; int n,m,w,fa[1001],dp[1001][2]; struct node{ int x,y; }e[1001]; vector <int> v[1001]; inline int find(int a){ if(fa[a]!=a) return fa[a]=find(fa[a]); return a; } inline void Jimmy(){ scanf("%d%d%d",&n,&m,&w); for(int i=1;i<=n;i++){ scanf("%d",&e[i].x); fa[i]=i; } for(int i=1;i<=n;i++) scanf("%d",&e[i].y); for(int i=1,a,b;i<=m;i++){ scanf("%d%d",&a,&b); int fx=find(a),fy=find(b); if(fx!=fy) fa[fx]=fy; } for(int i=1;i<=n;i++) v[find(i)].push_back(i); for(int i=1;i<=n;i++) if(find(i)==i){ for(int j=w;j>=1;j--){ int numa=0,numb=0; for(int k=0;k<v[i].size();k++){ numa+=e[v[i][k]].x; numb+=e[v[i][k]].y; if(j>=e[v[i][k]].x) dp[j][1]=max(dp[j][1],dp[j-e[v[i][k]].x][0]+e[v[i][k]].y); } if(j>=numa) dp[j][1]=max(dp[j][1],dp[j-numa][0]+numb); dp[j][0]=max(dp[j][0],dp[j][1]); } } printf("%d",dp[w][1]); } int main(){ Jimmy(); return 0; }
原文：http://www.cnblogs.com/JimmyC/p/6503172.html
