十五月明

用户名：dotcpp0605328

访问量：5011

签　名：

等　　级
排　　名	389
经　　验	5102
参赛次数	0
文章发表	78
年　　龄	18
在职情况	学生
学　　校	曲阜师范大学
专　　业	人工智能

　　自我简介：

Easy

TA的其他文章

信息学奥赛一本通T1346-亲戚(relation) 并查集此题有毒
浏览：4

信息学奥赛一本通T1347-格子游戏并查集
浏览：3

团伙(group) 并查集
浏览：16

你可能喜欢

搭配购买(buy) 并查集+01背包dp问题

　　作者: 十五月明　　　　发表时间：2024-10-21 22:16:42 浏览：4　|　评论：0　

原题链接：搭配购买(buy)

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4 + 5;
    int father[N];
    int value[N],cost[N];
    int dp[N];
    int n,m,w;
    
    int find(int x){
        if(father[x]!=x){
            x=find(father[x]);
        }
        return father[x];
    }
    
    void initial(){
        for(int i=1;i<=n;i++){
            father[i]=i;
        }
    }
    
    void Union(int a,int b){
        int x=find(father[a]);
        int y=find(father[b]);
        if(x!=y){
            father[x]=y;
        }
    }
    int main()
    {
        cin>>n>>m>>w;
        initial();
        for(int i=1;i<=n;i++) cin>>cost[i]>>value[i];
        for(int i=1;i<=m;i++){
            int b,c; cin>>b>>c;
            Union(b,c);
        }
        
        //memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            if (father[i] != i) {
                value[find(i)] += value[i];
                value[i] = 0;
                cost[find(i)] += cost[i];
                cost[i] = 0;
           }
        }
        for(int i = 1; i <= n; i++){
            for (int j = w; j>=cost[i]; j--){
                dp[j]=max(dp[j],dp[j-cost[i]]+value[i]);
           }
        }
        cout << dp[w]<<endl;
        return 0;
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

十五月明

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

Hello, world! （C语言代码）

人见人爱A+B （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C二级辅导-计负均正（C++代码）

搭配购买(buy) 并查集+01背包dp问题

评论区

精彩推荐

C语言训练-求函数值（C语言代码）

C二级辅导-阶乘数列（C语言代码）

震宇大神的杀毒软件（C++代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

关于C语言变量位置的问题

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

十五月明

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

Hello, world! （C语言代码）

人见人爱A+B （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C二级辅导-计负均正 （C++代码）

搭配购买(buy) 并查集+01背包dp问题

评论区

精彩推荐

C语言训练-求函数值 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

震宇大神的杀毒软件 （C++代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

关于C语言变量位置的问题

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C二级辅导-计负均正（C++代码）

　　评论区

C语言训练-求函数值（C语言代码）

C二级辅导-阶乘数列（C语言代码）

震宇大神的杀毒软件（C++代码）