首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >CSU 1326: The contest(分组背包)

CSU 1326: The contest(分组背包)

作者头像
用户1624346
发布于 2018-04-17 08:25:14
发布于 2018-04-17 08:25:14
64500
代码可运行
举报
文章被收录于专栏:calmoundcalmound
运行总次数:0
代码可运行

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326

题意:

      n个题目,每个题目都有一个价值Pi和相对能力消耗Wi,但是有些题目因为太坑不能同时做出来,并且坑题具有传递性。(a和b一起做会坑、b和c会坑则a和c也会坑) 它们最多可以作出多少价值的题目。

分析:先用并查集,将组分出来,然后进行分组背包

   注意F数组,数组开辟的大小应该为总价值的最大值,还有初始化别忘记了  

   以及j-pi[i]>=0 一维数组:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
const int MOD=1000000007;
const int MN=1010;
int father[MN];
int num[MN][MN];
int rank[MN];
int f[MN];
int val[MN],pi[MN];
int vis[MN];
int cnt[MN];
 
void Make_set(int n)
{
    for(int i=0; i<=n; i++)
    {
        father[i]=i;
    }
}
 
int Find(int x)
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
 
void Union(int x,int y)
{
    if(x==y) return ;
    father[x]=y;
}
 
int main()
{
    int i,j,k,n,m;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        Make_set(n);
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&val[i],&pi[i]);
        }
        int a,b;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&a,&b);
            int x=Find(a);
            int y=Find(b);
            Union(x,y);
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            int t=Find(i);
            vis[t]++;
        }
        int cas=0;
        for(i=1; i<=n; i++)
        {
            if(vis[i])
            {
                ++cas;
                int tes=0;
                for(j=1; j<=n; j++)
                {
                    if(father[j]==i)
                        num[cas][++tes]=j;
                }
                cnt[cas]=vis[i];
            }
        }
        memset(f,0,sizeof(f));
        for(i=1;i<=cas;i++)
        {
            for(j=m;j>=0;j--)
            {
                for(k=1;k<=cnt[i];k++)
                {
                    int xx=num[i][k];
                    if(j-pi[xx]>=0) f[j]=max(f[j],f[j-pi[xx]]+val[xx]);
                }
            }
        }
        printf("%d\n",f[m]);
    }
    return 0;
}

二维数组:

循环取最大值的那里要小心,始终要和f[i-1][j]进行比较

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
const int MOD=1000000007;
const int MN=1010;
int father[MN];
int num[MN][MN];
int rank[MN];
int f[MN][MN];
int val[MN],pi[MN];
int vis[MN];
int cnt[MN];
 
void Make_set(int n)
{
    for(int i=0; i<=n; i++)
    {
        father[i]=i;
    }
}
 
int Find(int x)
{
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
 
void Union(int x,int y)
{
    if(x==y) return ;
    father[x]=y;
}
 
int main()
{
    int i,j,k,n,m;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        Make_set(n);
        for(i=1; i<=n; i++)
        {
            scanf("%d%d",&val[i],&pi[i]);
        }
        int a,b;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&a,&b);
            int x=Find(a);
            int y=Find(b);
            Union(x,y);
        }
        memset(vis,0,sizeof(vis));
        for(i=1; i<=n; i++)
        {
            int t=Find(i);
            vis[t]++;
        }
        int cas=0;
        for(i=1; i<=n; i++)
        {
            if(vis[i])
            {
                ++cas;
                int tes=0;
                for(j=1; j<=n; j++)
                {
                    if(father[j]==i)
                        num[cas][++tes]=j;
                }
                cnt[cas]=vis[i];
            }
        }
        memset(f,0,sizeof(f));
        for(i=1;i<=cas;i++)
        {
            for(j=m;j>=0;j--)
            {
                for(k=1;k<=cnt[i];k++)
                {
                    int xx=num[i][k];
                    if(j-pi[xx]>=0)
                    {
                        f[i][j]=max(f[i][j],f[i-1][j-pi[xx]]+val[xx]);
                        f[i][j]=max(f[i-1][j],f[i][j]);
                    }
                    else f[i][j]=max(f[i][j],f[i-1][j]);
                }
            }
        }
        printf("%d\n",f[cas][m]);
    }
    return 0;
}

分组背包:http://www.nocow.cn/index.php/%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-10-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
虚拟机VMware上安装CentOS(详细图文教程)
1、进入 CentOS 官网:https://www.centos.org/download/
用户11124775
2024/06/12
6.6K0
VMware虚拟机黑群晖7.2 Beta (懒人包)
1. 首先解压安装包,双击解压出来的 DS923.vmx 配置文件. 导入到虚拟机
素颜520
2023/04/22
3.9K1
VMware虚拟机黑群晖7.2 Beta (懒人包)
VMware安装Mac系统
Mac 10.11.1系统下载:链接:pan.baidu.com/s/1693axsKP… 提取码:csly
Happyjava
2020/03/20
9830
VMware安装Mac系统
Mini小主机All-in-one搭建教程6-安装苹果MacOS系统
笔者使用的ESXI7.0 Update 3 抱着试试的态度想安装一下苹果的MacOS系统
星哥玩云
2023/10/19
3K0
Mini小主机All-in-one搭建教程6-安装苹果MacOS系统
VMware16虚拟机 安装MacOS
有很多小伙伴在使用虚拟机安装MacOS的时候,都没有Apple Mac OS X这个选项,所以无法安装成功
Hunter@Miracle
2022/08/26
1.7K0
VMware16虚拟机 安装MacOS
VMware Workstation 12添加开机启动项来达到开机后自动启用虚拟机的方法
由于服务器有限,有时会用VMware Workstation创建虚拟机搭建linux环境,每次电脑重启都要重新打开VM软件然后再单个开启虚拟机,不仅麻烦还费时间,所以决定添加开机自启VM后自动启动虚拟机。
拓荒者
2019/03/11
5.9K0
VMWare14 安装Mac OS系统(图解)
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/details/78505422
泥豆芽儿 MT
2018/09/11
4.4K0
VMWare14 安装Mac OS系统(图解)
macOS虚拟机安装全过程(VMware)
作为一名忠实果粉,我最大的愿望就是能够拥有一台Macbook,体验macOS,但是作为学生党,这价钱,贵到离谱啊~~~
全栈程序员站长
2022/09/22
33.6K8
macOS虚拟机安装全过程(VMware)
虚拟机怎么安装vmware tools
这篇文章主要为大家详细介绍了VMware Workstation12安装Ubuntu和VMware Tools教程,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
全栈程序员站长
2022/09/01
1.8K0
虚拟机怎么安装vmware tools
使用VMware虚拟机安装最新版Mac OS 10.14教程
突发奇想,想在虚拟机里面弄个黑苹果,于是开始了操作,清理了40g的磁盘空间进行安装。
Lcry
2022/11/29
1.2K0
使用VMware虚拟机安装最新版Mac OS 10.14教程
VMWare14 安装Mac OS系统(操作图解)
②. 网上的镜像文件有的可能不是 .cdr 格式,比如我之前安装的是 .pkg 格式报的蓝屏启动界面,此处以 .cdr 文件为操作指导。
全栈程序员站长
2022/09/05
1.6K0
VMWare14 安装Mac OS系统(操作图解)
vmware虚拟机文件_怎么往虚拟机里复制文件
虚拟机的文件管理由VMware Workstation来执行,一个虚拟机一般以一系列文件的形式储存在宿主机中,这些文件一般在由workstation为虚拟机所创建的那个目录中。 这里列出了这些关键文件的扩展名。在这些例子中,<vmname>表示你的虚拟机名字。
全栈程序员站长
2022/09/20
2K0
Linux实验用的软件(包括VMware 和VirtualBox虚拟机软件)
实验软件下载方法录像:https://mp.weixin.qq.com/s/Qt2UqmTTLPUJyl04Vttxjg
姚远OracleACE
2023/04/06
1K0
Linux实验用的软件(包括VMware 和VirtualBox虚拟机软件)
AMD电脑要搞macOS虚拟机的话最好用10.15之前的版本,个人实测10.14.6很稳定
Apple公司在macOS 10.15之后推出了ARM架构M芯片处理器,不再用Intel处理器(AMD跟Intel都是x86架构,AMD跑macOS虚拟机需要特殊处理.vmx文件)
Windows技术交流
2024/07/19
1.2K0
【第15期】如何在VMware Workstation上安装MacOS系统
想在Windows系统上面,运行macOS系统,最简单的方式就是在VMware Workstation上安装macOS。不过,我发现在VM上面运行macOS系统的缺点是,运行极其缓慢,即使我已经给macOS分配了4GB的内存。
siberiawolf
2020/03/24
5.3K0
【第15期】如何在VMware Workstation上安装MacOS系统
操作系统 | 虚拟机及linux的安装
完成虚拟机及linux的安装RedHat9已安装成功(使用虚拟机打开.vmx文件即可)链接 提取码:ry14https://pan.baidu.com/s/1yejuznzVRhsj29zpFnJedw?pwd=ry14
SarPro
2024/02/20
2970
操作系统 | 虚拟机及linux的安装
Vmware安装MacOS
Vmware安装懒得说,主要讲系统安装 Vmware是没有安装mac系统这个选项的 所以需要unlocker 解压了之后,管理员方式运行 win-install.cmd安装完后打开Vmware后就可以看到这个选项了
Elapse
2020/08/17
1K0
VMware虚拟机安装黑群晖7.0教程
大家好,又见面了,我是你们的朋友全栈君。 教程仅供参考,不当之处多多理解。 本篇教程主要讲解黑群晖(DS918+)的详细安装教程 Tip: 本教程本教程只用学习使用,有条件,长期使用的朋友推荐从正规官方渠道入手。 1.首先安装VMware虚拟机 双击安装文件进行安装 2.打开安装程序后 点击下一步 3.点击我接受许可协议 下一步 4.选择安装位置 点击下一步 5.继续点击下一步 6.点击下一步 7.点击安装 8.耐心等待安装 9.点击许可证进行激活 10.输入许可证秘
全栈程序员站长
2022/09/14
5.6K0
VMware虚拟机安装黑群晖7.0教程
使用VMware安装Ubuntu虚拟机
  这一步跳过,因为网上都能找到下载地址,下载后一步一步的安装即可,网上也有很多下载地址,这里提供一个Windows的下载链接。
Se7eN_HOU
2022/06/12
7410
使用VMware安装Ubuntu虚拟机
Windows搭建mac黑苹果系统
最近看到一个开源工具 tidevice ,是可以脱离mac来做ios自动化测试的。看到这么方便,就想着来尝尝鲜。但由于使用该工具,是需要基于 WebDriverAgent 的,该工具又需要使用Xcode重签名安装。手边没有mac电脑,所以就装个黑苹果来捣鼓下吧。安装过程并不顺利,也有失败的经历。想了想,还是写篇博文记录下,也算是爬坑了。
用户10106350
2022/10/28
2.7K0
Windows搭建mac黑苹果系统
推荐阅读
相关推荐
虚拟机VMware上安装CentOS(详细图文教程)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验