给出一群女孩的重量和颜值 和她们的朋友关系 现在有一个舞台 ab是朋友 bc是朋友 ac就是朋友 给出最大承重 可以邀请这些女孩来玩
对于每一个朋友团体 全邀请or邀请一个or不邀请 问能邀请的女孩的最大颜值
比赛的时候一看就是个背包问题 似乎在背包九讲上面见过..但是不会写
于是百度.."背包 一类选一个"
百度出了分组背包 并且第一个搜索结果就是类似于原题的东西..
只不过分组背包的模板是一个or不要 加了个bfs 把朋友团体作为一个新朋友加入进这个团体 改了改代码..就a了..
虽然fst掉了c...
后来学习了一下 发现分组背包是这样写的
for(int i=1;i<=n;i++)枚举每一个分组
for(int j=V;j>=0;j++)枚举背包容量
for(int k=1;k<=x;k++)枚举i分组里面的所有物品
dp[j] = max(dp[j],dp[j-vol[k]]+val[k]);
当然二维的比较好理解...
在这个题中 并查集和bfs统计朋友团体都可以
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
#include<malloc.h>
using namespace std;
#define L long long
vector<int >q[1050];
int val[2050];
int vol[2050];
int dp[1050];
int n,m,w;
int id[1050];
vector<int >z[1050];
void bfs(int u,int cnt){
int sumval = 0;
int sumvol = 0;
queue<int>que;
que.push(u);
id[u] = cnt;
sumval += val[u];
sumvol += vol[u];
z[cnt].push_back(u);
while(!que.empty()){
int f=que.front();que.pop();
for(int i=0;i<q[f].size();i++){
int v=q[f][i];
if(id[v] == -1){
z[cnt].push_back(v);
sumval += val[v];
sumvol += vol[v];
id[v] = cnt;
que.push(v);
}
}
}
val[cnt + n] = sumval;
vol[cnt + n] = sumvol;
z[cnt].push_back(n + cnt);
}
int main(){
scanf("%d%d%d",&n,&m,&w);
for(int i=1;i<=n;i++)scanf("%d",&vol[i]);
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int i=1;i<=n;i++)q[i].clear();
memset(id,-1,sizeof(id));
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
q[u].push_back(v);
q[v].push_back(u);
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(id[i] == -1){
cnt ++;
z[cnt].clear();
bfs(i,cnt);
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=cnt;i++){
for(int j=w;j>=0;j--){
for(int k=0;k<z[i].size();k++){
int d=z[i][k];
if(j>=vol[d]){
if(dp[j]<dp[j-vol[d]]+val[d]){
dp[j]=dp[j-vol[d]]+val[d];
}
}
}
}
}
printf("%d\n",dp[w]);
}