十五月明

用户名：dotcpp0605328

访问量：5439

签　名：

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

　　自我简介：

Easy

TA的其他文章

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

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

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

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

　　作者: 十五月明　　　　发表时间：2024-10-21 22:16:42 浏览：12　|　评论：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语言程序设计教程（第三版）课后习题7.4 （C语言代码）

矩阵转置（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

程序员的表白（C语言代码）

字符串问题（C语言代码）

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

评论区

精彩推荐

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

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

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

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

C二级辅导-进制转换（C语言代码）

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

C语言训练-8除不尽的数（C语言代码）

小O的乘积（C语言代码）

陶陶摘苹果（C语言代码）

P1025 （C语言代码）

十五月明

TA的其他文章

你可能喜欢

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

矩阵转置 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

程序员的表白 （C语言代码）

字符串问题 （C语言代码）

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

评论区

精彩推荐

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

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

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

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

C二级辅导-进制转换 （C语言代码）

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

C语言训练-8除不尽的数 （C语言代码）

小O的乘积 （C语言代码）

陶陶摘苹果 （C语言代码）

P1025 （C语言代码）

矩阵转置（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

程序员的表白（C语言代码）

字符串问题（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

C语言训练-8除不尽的数（C语言代码）

小O的乘积（C语言代码）

陶陶摘苹果（C语言代码）