【图论】网络流——最大流和最小费用流文章目录【图论】网络流——最大流和最小费用流1.最大流问题1.1基本概念1.2寻求最大流的算法（Ford-Fulerson）1.3matlab求最大流2.最小流问题2.1基本概念2.2求最小流的迭代算法2.3matlab求最大费用最小流1.最大流问题主要解决系统中的流量问题：如公路系统中的车辆流、物资调配系统中的物资流、金融系统中的现金流等。这些问题都可以归结为网络流问题，如何安排使流量最大即最大流问题。什么是最大流？如左图能输送两份的水，是最大流；右图只能输送一份的水，不是最大流1.1基本概念网络：图D=(V,A,C)D=(V,A,C)D=(V,A,C)V
目录T1[Daimayuan]Collision（C++，多源最短路）题目描述输入描述输出描述样例输入1样例输出1样例输入2样例输处2数据范围解题思路T2[Daimayuan]农田划分（C++，数学，BFS）题目描述题目输入题目输出样例输入1样例输出1样例输入2样例输出2数据范围解题思路T3[Daimayuan]三段式（C++，数组前缀和）输入描述输出描述样例输入样例输出样例解释解题思路T4[Daimayuan]模拟输出受限制的双端队列（C++，模拟）输入格式输出格式样例输入样例输出数据规模解题思路T5[Daimayuan]简单差分（C++，线段树）输入格式输出格式样例输入样例输出数据规模解题
本文主要解决以下几个问题：1.欧拉图能不能有割点，能不能有桥？2.哈密顿图能不能有割点，能不能有桥？首先我们要明白几个定义割点的定义就是在一个图G中，它本来是连通的，去掉一个点v以后这个图G就不连通了，那么点v就被叫做割点。桥的定义就是在一个图G中，它本来也是连通的，去掉一条边x以后这个图就不连通了，那么边x就被称为桥。欧拉图是拥有欧拉闭迹的图。所谓欧拉闭迹，包含两层概念：“闭”和“迹”。我们先来说什么是迹，所谓“迹”，就是用一笔可以从一个顶点出发，一直沿着边走，走到另一个顶点停止。在走的过程中，可以有重复的点，但是不能有重复的边。也就是说一个点可以经过两次以上，但是一个边只能走一次。 如图：
图的基本概念1图1.1图的定义定义1：一个无向图G是一个有序的二元组，其中（1）V是一个非空有穷集，称为顶点集，其元素称为顶点或结点。（2）E是无序积V&V的有穷多重子集，称为边集，其元素称为无向边，简称边。定义2：一个有向图D是一个有序的二元组，其中（1）V是一个非空有穷集，称为顶点集，其元素称为顶点或结点。（2）E是笛卡尔积VXV的有穷多重子集，称为边集，其元素称为有向边，简称边。在图G中,如果每条边都是有向边,该图称为有向图(DirectedGraph)若每条边都是无向边,该图G称为无向图(UndirectedGraph)如果有些边是有向边,另一些边是无向边,图G称为混合图(MixedG
A:::::::::::::::::::::::::::::::::::m计划（双指针，滑动窗口，倍增）题目描述小明是个鹅卵石收藏者，从小到大他一共收藏了 nn 块鹅卵石，编号分别为1∼n，价值分别为a1，a2，⋯,an。这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所在的海域下起了暴雨。很快小明船上的积水越来越多，为了防止沉船，小明不得不选择若干块他收藏的鹅卵石丢弃。小明制定了一套名为m计划的选择方案，其内容如下：对于任意区间 [i,i+m-1]丢弃价值最小的鹅卵石i∈[1,n−m+1]。对于一块鹅卵石，它在 m 计划中是可以被丢弃多次的。请你输出将被小明丢弃的鹅卵石的价值。输入描
A:::::::::::::::::::::::::::::::::::m计划（双指针，滑动窗口，倍增）题目描述小明是个鹅卵石收藏者，从小到大他一共收藏了 nn 块鹅卵石，编号分别为1∼n，价值分别为a1，a2，⋯,an。这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所在的海域下起了暴雨。很快小明船上的积水越来越多，为了防止沉船，小明不得不选择若干块他收藏的鹅卵石丢弃。小明制定了一套名为m计划的选择方案，其内容如下：对于任意区间 [i,i+m-1]丢弃价值最小的鹅卵石i∈[1,n−m+1]。对于一块鹅卵石，它在 m 计划中是可以被丢弃多次的。请你输出将被小明丢弃的鹅卵石的价值。输入描
目录一、引入图论 二、图的基本概念与数据结构1.基本概念 2.图与网络结构1.邻接矩阵表示法 2.稀疏矩阵表示法三、最短路径问题1、迪杰斯特拉（Dijkstra）算法2、贝尔曼-福特（Bellman-Ford）算法3、弗洛伊德（Floyd）算法一、引入图论 图论起源于18世纪，近几十年来，计算机技术与科学的飞速发展，大大促进了图论的研究与应用，图论的理论和方法已经渗透到物理、化学、通信科学、建筑学、运筹学、生物遗传学、心理学、经济学、社会学等学科中。 图论所谓的“图”是指某类具体事物和这些事物之间的联系。如果用点表示这些具体事物，用连接两点的线段（直的或者曲的）表示
作者：指针不指南吗专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾文章目录1.路径2.特别数的和3.MP3储存4.求和1.路径题目链接：路径-蓝桥云课(lanqiao.cn)本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由2021个结点组成，依次编号1至2021。对于两个不同的结点a,b，如果a和b的差的绝对值大于21，则两个结点之间没有边相连；如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和b的最小公倍数的无向边相连。例如：结点1和结点2
作者：指针不指南吗专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾文章目录1.路径2.特别数的和3.MP3储存4.求和1.路径题目链接：路径-蓝桥云课(lanqiao.cn)本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由2021个结点组成，依次编号1至2021。对于两个不同的结点a,b，如果a和b的差的绝对值大于21，则两个结点之间没有边相连；如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和b的最小公倍数的无向边相连。例如：结点1和结点2
图的遍历——深度优先遍历深度优先搜索（DepthFirstSearch，DFS）是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。深度优先遍历是按照深度优先搜索的方式对图进行遍历的。深度优先遍历的秘籍：后被访问的节点，其邻接点先被访问。根据深度优先遍历的秘籍，后来者先服务，这可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归的方法更方便。【算法步骤】①初始化图中的所有节点均未被访问。②从图中的某个节点v出发，访问v并标记其已被访问。③依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复步骤2～3）。【完美
