社区讨论

这数据没谁了

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 条回复,欢迎继续交流。

正在加载回复...