社区讨论
这数据没谁了
P1455搭配购买参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mmc4cscz
- 此快照首次捕获于
- 2026/03/04 22:15 4 天前
- 此快照最后确认于
- 2026/03/07 14:45 22 小时前
这能90分?
我将每个组的值赋给属于这个组的所有元素,明显这是错的,因为每一个组应该当做一件物品来看待,结果
CPP#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define div() cout << "\n-----------------------\n";
#define debug(n) cout << #n << " = " << n << "\n";
#define deb(n) cout << #n << " = " << n << " ";
int n,m,W;
struct cloud{int w,v,group;}a[10005];
bool cmp(cloud x, cloud y){return x.group < y.group;}
int groups[10005];int gnumv[10005],gnumw[10005];
vector<int>l[10005];
bool vis[10005];int cnt;
int dp[10005];
void dfs(int now,int groupnum){
vis[now] = 1;a[now].group = groupnum;
for(auto x : l[now]){
if(!vis[x]){dfs(x,groupnum);}
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> W;
for(int i = 1;i <= n;i++){cin >> a[i].w >> a[i].v;}
for(int i = 1;i <= m;i++){
int u,v;cin >> u >> v;
l[u].push_back(v);l[v].push_back(u);
}
for(int i = 1;i <= n;i++){if(!vis[i]){dfs(i,++cnt);}}
sort(a+1,a+n+1,cmp);
int sumw = a[1].w,sumv = a[1].v;
for(int i = 2;i <= n+1;i++){
if(a[i].group != a[i-1].group){
gnumv[a[i-1].group] = sumv;gnumw[a[i-1].group] = sumw;
sumv = a[i].v;sumw = a[i].w;
}
else{sumw += a[i].w;sumv += a[i].v;}
}
for(int i = 1;i <= n;i++){
a[i].v = gnumv[a[i].group];
a[i].w = gnumw[a[i].group];
}
for(int i = 1;i <= n;i++){
for(int j = W;j >= a[i].w;j--){
dp[j] = max(dp[j],dp[j-a[i].w] + a[i].v);
}
}
cout << dp[W];
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...