最小点覆盖问题详解

2023-11-02

那么一如既往,还是个人觉得学习某一个知识点之前先粗俗的了解其是个什么东东,然后再去了解概念比较好...那么下面结合题目来了解:

首先最最重要的是理解题意,有k个任务,每个任务task_i可以用机器A的x_i模式做,也可以由机器B的y_i模式做(值得注意的是只有两个机器,但是有不同的模式,每次可以在一个模式下工作),在做所有的任务之前,A与B的模式都最开始调为0,为了把所有任务做完,我们需要按照不同的任务,调制机器A或者B的模式,那么,我们最少要调制机器多少次,能完成所有的任务?
比如
任务task_0要么由A的模式0完成,要么由B的模式1完成,
任务task_1要么由A的模式1完成,要么由B的模式0完成,
那么我们要调整机器多少次呢?
首先机器的模式都是0(再次说明题目中最开始的模式是0),用A的0先完成task_0,用B的0完成task_1就可以啦...所以,我们一次都不用调制
但是如果还有几个个任务
task_2要用A的1模式,或者B的2模式,
task_3要么由A的2模式要么B的2模式完成    ..你要调制机器几次呢?
可以有以下几个方案:
1.调制A从0到1,完成task_2,然后调制A从1到2,完成task_3---总共调制2次
2.调制A从0到1,完成task_2,然后调制B从0到2,完成task_3---总共调制也是2次
3.调制B从0到2,那么就可以同时完成task2,task_3,-----------总共调制1次

到这里,题目都差不多描述完啦,那么下面就是粗俗了解”最小点覆盖“这个新东西,并且如何将其和题目结合

1.首先画图来理解“最小点覆盖”,就拿我们上面的例子来说,(先不管最小点覆盖这个概念)最开始把task和机器联系起来(就是task_i能给哪个机器的哪个模式做就连一条线),联系起来之后便是如下:

从图中看,结合最开始的题意理解,可以知道task0和1都让A的0模式做,task2,3都让B的模式2去做可以达到题目要求:最少调整机器的次数,现在我们就把要做的工作当做联系A、B机器的线(从图中看得出每一个任务把机器的模式连接起来),简化为下图:

那么现在我们A的0模式邻接了2条边,B的2模式邻接了2条边,我们知道边就是任务,图中的圆圈就是机器的模式,那么现在就题目就成了我们选最少的点(机器模式),可以邻接更多的线(任务),那么我们把邻接叫做覆盖,也就是说成了选最少的点,去覆盖尽可能多的边.....嘿嘿,是不是觉得"最小点覆盖"有那么点概念了呢?

那么根据公式 :最小点覆盖=最大匹配 如果想知道为啥,推荐一个:最小点覆盖证明

 

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

最小点覆盖问题详解 的相关文章

  • win系统电脑如何打开sketch?

    2 个方法快速使用 Windows 系统打开 Sketch 文件 使用 Adobe XD 打开 Sketch 文件或者使用浏览器中就能做设计的即时设计直接打开 Sketch 文件 众所周知 Sketch 只能在 Mac 电脑上使用 因此只有
  • SQuirrel SQL Client数据库连接工具的配置与使用

    SQuirrel SQL Client介绍 SQuirrel SQL Client是一个用Java写的数据库客户端 用JDBC统一数据库访问接口以后 可以通过一个统一的用户界面来操作MySQL PostgreSQL MSSQL Oracle
  • Java Html嵌入applet 来读取客户端串口

    写在前面 之前没搞过html嵌入applet来读取本地客户端串口 就直接使用RXTXcom jar 来直接读取本机串口 这个是没问题的如下 RXTX 有三个文件 有针对操作系统64 还有32的 1 RXTXcomm jar 导入项目中 2
  • 【LaTeX】矢量图转为pdf格式(为了将高清矢量图插入LaTeX)

    在论文编写的时候 需要插入高清的矢量图 但是不同的图片生成软件 图片处理软件 论文编写软件所支持的矢量图格式都是不一致的 如 matplotlib可以保存的矢量图格式为 svg eps 等 visio可以保存的格式为 svg emf 等 但
  • 聊聊 Java 泛型

    概述 什么是泛型 为什么需要泛型 如何使用 是什么原理 如何改进 这基本上就是我们学习一项技术的正确套路 本文将按照以上顺序展开阐述 介绍我所了解的泛型 什么是泛型 泛型的本质是参数化类型 即给类型指定一个参数 然后在使用时再指定此参数具体
  • Unable to start web server; nested exception is org.springframework.boot.web.server.WebServerExcepti

    问题描述 在异常信息当中我发现到一个redis连接不上的异常 项目当中我使用的是多环境 我运行的时候是运行的dev 这里的 profile active 我们在idea的maven的配置处进行快速的切换 启动项目的时候报的是连接不上redi
  • RabbitMq基础篇-09-channel接口常用几种参数详解

    文章目录 1 背景概述 2 通常参数解释 3 Channel一些Api解释 3 1 basicNack 不确认消息 3 2 basicReject 拒绝消息 3 3 RecoverOk 是否恢复消息到队列 3 4 exchangeDecla
  • PM产品经理面试 面经汇总

    系列文章目录 第一章 如何找到一份PM产品经理的工作 第二章 PM 面试技巧 文章目录 系列文章目录 一 PM面试准备 二 面试流程 1 行测 2 Behavioral Question 3 product design question
  • MySQL--主从复制--01--原理

    MySQL 主从复制 01 原理 一 故事 爸爸在酒店做厨师 正准备做西红柿炒蛋 妈妈也想做 于是让女儿给爸爸打电话 爸爸接到电话后 于是就把他目前正在做的事情 洗菜 切菜 告诉女儿 女儿记在笔记里 妈妈看笔记 按笔记的内容做菜 就这样爸爸
  • 绝对想不到,Chatgpt 优缺点都有这些

    ChatGPT 是一种基于自然语言处理 NLP 模型的对话生成程序 它的核心是通过机器学习算法训练得到的语言模型 GPT Generative Pre trained Transformer 是ChatGPT的基础 这是一种使用Transf
  • 寻找一维数组的连续数值波峰波谷

    如果一维数组中有波峰和波谷 但是波峰会持续好几个同样的数值或者差异很小而不是只有一个数值 波谷同理 要去寻找这种类型的波峰波谷就会有点难度 数据类似这种 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0016790
  • AH协议与ESP协议简析

    http www gxu edu cn college hxhgxy sec COURSE ch12 2 1 htm http www gxu edu cn college hxhgxy sec COURSE ch12 2 2 htm ht
  • MATLAB实现dijkstra算法的障碍物规避

    MATLAB实现dijkstra算法的障碍物规避 在自主导航系统中 机器人需要能够避开障碍物以安全地到达目标点 其中 dijkstra算法是一种常用的路径规划算法 能够在无权重图中求解最短路径 在本篇文章中 我们将介绍如何使用MATLAB实
  • Java 的VO、DTO、TO、BO等概念总结

    当涉及到Java中的数据传输和对象封装时 有几个常见的概念 它们在不同的上下文中具有不同的用途 以下是这些概念的总结 VO Value Object 含义 VO表示值对象 用于封装一组相关的数据字段 通常没有业务逻辑 用途 VO通常用于数据
  • PBFT共识算法原理

    1 容错类型 PBFT假定错误可以是拜占庭类型的 也就是说可以使任意类型的错误 比如节点作恶 说谎等 这有别于crash down类型的错误 raft paxos这类共识算法只能允许crash down类型错误 节点只能crash而不能产生
  • 推荐三款适合运维小白的网络监测工具

    对于刚刚步入职场的运维小白而言 面对工作中的突发情况时常会感到手忙脚乱 为了帮助他们更好地应对这些挑战 本文将介绍三款特别适合运维新手使用的网络监测工具 1 Zabbix是一个功能强大的网络监控系统 可以监视各种网络设备的性能指标 应用的运
  • Python图形界面设计 Tkinter GUI编程组件的使用

    一 学习目标 1 GUI库 2 Tkinter库 3 导入Tkinter库 4 4 Tkinter窗口中显示中文 5 Tkinter 组件 二 重点知识 1 GUI库 GU1 Graphical User Interface 图形用户界面
  • 【Python数据挖掘课程】二.Kmeans聚类数据分析及Anaconda介绍

    这次课程主要讲述一个关于Kmeans聚类的数据分析案例 通过这个案例让同学们简单了解大数据分析的基本流程 以及使用Python实现相关的聚类分析 主要内容包括 1 Anaconda软件的安装过程及简单配置 2 聚类及Kmeans算法介绍 3
  • 使用SoapHeader实现Soap请求验证

    http www laruence com 2010 03 26 1365 html PHP的Soap Extension中 对于SoapServer来说 并没有方法可用得到 处理客户端发送的SoapHeader信息 网上也有很多人认为 只

随机推荐

  • CSS&JavaScript讲解

    CSS 概念 全称 Cascading Style Sheets 层叠样式表 用于美化页面 布局页面 层叠 多个样式可以作用在同一个html的元素上 同时生效 好处 功能强大 将内容展示和样式控制分离 降低耦合度 解耦 让分工写作更容易 提
  • QQ分享失败原因

    通过qq分享链接到QQ空间 QQ当中 分享失败 要么就是调起qq后调不起分享框 排查了很久才找到原因 原来是分享的url链接不正确
  • PAT-B 1032 挖掘机技术哪家强 (20分)

    为了用事实说明挖掘机技术到底哪家强 PAT 组织了一场挖掘机技能大赛 现请你根据比赛结果统计出技术最强的那个学校 输入格式 输入在第 1 行给出不超过 10 5 的正整数 N 即参赛人数 随后 N 行 每行给出一位参赛者的信息和成绩 包括其
  • leetcode3 链表相加

    package 剑指offer 我们要明白链表逆序的好处 4 gt 2 gt 5 5 gt 8 gt 1 9 gt 0 gt 7 第一 数需要对齐 尤其是两个数不是相同位数的情况 那么那就回想一下 我们做加法都是尾部对齐 而不是头部 这样的
  • 如何在pycharm使用Anaconda下载的库

    如何在pycharm使用Anaconda下载的库 这篇文章 介绍了如何在pycharm项目 project 里建立Anaconda环境 从而引用anaconda下载的库 site packages 但我个人使用后发现 换了虚拟环境后无法实现
  • 旋转的矩阵-c++

    旋转的矩阵 数据结构 题目描述 给定一个n m的矩阵 请以顺 逆时针交替旋转的方式打印出每个元素 Input Format 第一行n m 0
  • Error getting generated key or setting result to parameter object. Cause: org.apache.ibatis.executor

    报错信息 Error getting generated key or setting result to parameter object Cause org apache ibatis executor ExecutorExceptio
  • 毕业设计课题大全

    Java毕业设计课题大全 https blog csdn net My IT Road article details 90341793 软件工程毕业设计集合 https blog csdn net linzhiqiang0316 arti
  • tutk云平台服务器_哪家云服务器便宜?各家云平台活动详解【持续更新】

    不知不觉 双十一已经近在眼前 作为一年一度的购物狂欢节 无论对于商家还是消费者来说 都是一次畅快购物的饕餮盛宴 对于云平台来说 自然不会错过一年中绝佳的营销机会 各种优惠活动也是纷至沓来 在讨论哪家云服务器便宜之前 我们先来看看该如何选择云
  • 微信登录总结公众号登录小程序登录企业微信登录

    微信公众号 服务号登录 微信内部网页授权 第一步 请求CODE https open weixin qq com connect oauth2 authorize appid APPID redirect uri REDIRECT URI
  • VC6.0打开文件以及向工程中添加文件时程序崩溃自动退出

    换了一台电脑 vc6 0程序中 点击打开文件以及向工程中添加文件时 程序竟然崩溃自动退出了 不知什么原因 安装相同的vc程序 本本竟然出现此缘故 但是这个操作又是自己经常用到的 所以不得不解决 与上一台电脑不同的是 此电脑是win7系统 而
  • 最小二乘拟合平面——拉格朗日乘子法

    目录 一 算法原理 二 代码实现 1 python 2 matlab 三 算法效果 一 算法原理 设拟合出的平面方程为 a x b
  • tinyhttp

    博客园 http www cnblogs com letlifestop Tinyhttpd 是J David Blackstone在1999年写的一个不到 500 行的超轻量型 Http Server 用来学习非常不错 可以帮助我们真正理
  • c++中和c语言不相同的地方

    c 糅合了c语言的语法 并且在c语言的基础上进行了改进 并且具有向下兼容的特性 但是c 改进了什么东西呢 今天就来学习一下吧 目录 命名空间 namespace cout与cin与endl 流插入符与流运算符 using namespace
  • [MySql]JDBC编程

    JDBC 即Java Database Connectivity java数据库连接 是一种用于执行SQL语句的Java API 它是Java中的数据库连接规范 这个API由 java sql javax sql 包中的一些类和接口组成 它
  • Vite unplugin-auto-import插件 自动引入组件

    文章目录 一 参考 二 快速入门 三 开发问题 3 1 解决eslint 报错的问题 3 2 解决 typescritp 报错的问题 unplugin auto import 自定义配置说明 一 参考 unplugin auto impor
  • QT textBrowser 设置每个字符串的颜色和大小

    QT textBrowser 设置每个字符串的颜色和大小 QT中textBrowser每行显示不同颜色 解决 Qt textBrowser 每行字体设置中的 n 缺失问题 原理 字体采用 html语言进行设置 方法 1 需要采用 appen
  • windows10 mvn安装后不是内部命令

    好气啊 maven 命令不识别 扒拉了半天 结果把全路径仍path一份就好使了 先记着吧
  • VS2010中C#调用C函数

    VS2010中C 调用C函数 2013 07 22 16 12 50 转载 分类 C Concept 1 创建C本地DLL文件 1 1 创建Win32Dll项目 1 2 创建DLL 点击完成 1 3 在 头文件 里新建文件 CPPLibra
  • 最小点覆盖问题详解

    那么一如既往 还是个人觉得学习某一个知识点之前先粗俗的了解其是个什么东东 然后再去了解概念比较好 那么下面结合题目来了解 首先最最重要的是理解题意 有k个任务 每个任务task i可以用机器A的x i模式做 也可以由机器B的y i模式做 值