最大流之二分图匹配二分图匹配模型匈牙利算法的复杂度为O(nm)O(nm)O(nm)最大流(Dinic)复杂度为O(mn)O(m\sqrt{n})O(mn​)。二分图匹配问题见图方式较为固定，设两个集合男孩集合A和女孩集合B进行配对，首先从源点向女生集合(男生具体哪个集合连源点根据题目所给的边决定)中的所有点连一条边，从另外一个集合中所有点向汇点连一条边，边权均为1跑最大流即为二分图匹配数。飞行员配对方案根据题意可得，外籍飞行员和英国本土飞行员两两成为一组，典型的二分图匹配问题，输出的答案为二分图匹配数，直接上最大流集合。建图大致如下：证明：​(1)、流量守恒：对于每个点都有两种可能，一是成功找

704.二分查找https://leetcode.cn/problems/binary-search/二分查找类似于查字典，每次找一半。需要注意的是二分时区间的选取。大多数情况选用左闭右闭和左闭右开两种方式。左闭右闭：classSolution{public:intsearch(vector&nums,inttarget){intleft=0,right=nums.size()-1;while(lefttarget)right=middle-1;elseif(nums[middle]用[1,1]做例子可知left可以等于right，但是比较时不能用等于，会重复上次循环的数据，并且left，ri

14天阅读挑战赛努力是为了不平庸~算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！❤️一名热爱Java的大一学生，希望与各位大佬共同学习进步❤️🧑个人主页：@周小末天天开心各位大佬的点赞👍收藏⭐关注✅，是本人学习的最大动力感谢！📕该篇文章收录专栏—趣学算法目录引入分治算法要素分治算法秘籍二分搜索算法题目问题分析算法步骤完美图解算法详解 算法分析 （1）时间复杂度：（2）空间复杂度：引入       现实生活中也有很多这样的例子，例如唱歌比赛，如果全国各地的歌手都来报名参赛，那么比赛就需要很长的时间，那怎么办呢？首先全国分赛区海选，然后每个赛区的前几名参加二分“海选”，最后选出比较优

1、704.二分查找    思路：        对于二分查找，主要是两个定义，左闭右闭[lift,right]、左闭右开[lift,right);        主要还是在程序里，当在while(lift中，左闭右闭是有意义的。此时更新        right=middle-1因为在判断里target已经是不等于数组下标middle对应的数。      classSolution{public:intsearch(vector&nums,inttarget){intleft=0;intright=nums.size()-1;while(lefttarget){right=middle-1;

704. 二分查找简单给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例 2:输入:nums=[-1,0,3,5,9,12],target=2输出:-1解释:2不存在nums中因此返回-1提示：你可以假设 nums 中的所有元素是不重复的。n 将在 [1,10000]之间。nums 的每个元素都将在 [-9999,9999]之间。第一种方法左闭右开clas

Leetcode704二分查找题目链接：704.二分查找思路：二分查找前提：有序数组，无重复数据1、确定有效区间，左闭右开，左闭右闭2、根据有效区间，写边界条件3、把有效的结果返回注意事项：取中间下角标的时候，需要注意超界问题。方法1右移位运算letmiddle=left+(right-left)>>1;方法2需要注意的是，JS并没有定义变量为整型数据的能力，需要自己手动向下取整。letmiddle=Math.floor(left+((right-left)/2));时间复杂度O(logn)空间复杂度O(1)Typescript代码左闭右闭letnums:number[]=[-1,0,3,5,

最小生成树Prim算法朴素版PrimO(n^2)稠密图步骤：S：表示最小生成树的集合初始化距离找距离集合S最近的节点将节点加入集合S用该节点更新非S点到集合S点的距离代码：constintN=510;constintINF=0x3f3f3f3f;intg[N][N];intd[N];//非生成树节点与生成树节点的最短距离intst[N];intn,m;intprim(){memset(d,0x3f,sizeofd);//初始化intres=0;//记录生成树权值和for(inti=0;i>n>>m;memset(g,0x3f,sizeofg);while(m--){intu,v,w;cin>>

一、引入（定义）小明："小张，我问你一个问题：在1,3,5,6,7,9这些数中5在那个位置？"小张："这还不简单，5在第三个位置！我是按顺序来找的：1,3,5。"小明："那我告诉你1~100这些数，让你找其中100这个数，你也从1~100来一个一个数吗？"小张："那我会从100~1来数。"小明："那如果你是一个机器人，我再问你这个问题，问：55在哪个位置？可是你只能从1~100或100~1来数数，可是这样数太慢啦！"小张："那可以怎们来数呢？"小明："这就要用到二分法的方法来解决啦！"二分法，是指将一个有序的数列中查找某个东西的位置或最大值、最小值、极值等一种比较快速的方法。做法是先找出数列中

文章目录二分图介绍染色法判定二分图例题：860.染色法判定二分图匈牙利匹配二分图最大匹配匈牙利匹配算法思想例题：861.二分图的最大匹配二分图介绍https://oi-wiki.org/graph/bi-graph/二分图是图论中的一个概念，它的所有节点可以被分为两个独立的集合，每个边的两个端点分别来自这两个不同的集合。换句话说，二分图中不存在连接同一集合内两个节点的边。染色法判定二分图如何判断一个图是二分图？当且仅当图中不含奇数环。（奇数环指的是环中边的个数是奇数）（因为每一条边都是从一个集合走到另一个集合，只有走偶数次才有可能回到同一个集合。）染色：相邻的节点的颜色不一样。因为没有奇数环，

题目链接：力扣题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例 2:输入:nums=[-1,0,3,5,9,12],target=2输出:-1解释:2不存在nums中因此返回-1提示：数组为升序，可以假设 nums 中的所有元素是不重复的。n 将在 [1,10000]之间。nums 的每个元素都将在 [-9999,9999]之间。解法一：二分法左闭