当前位置: 开发笔记 > 后端 > 正文

网络流(最小割)问题中的基础构图及分析方法小结

作者：null5269 | 来源：互联网 | 2023-07-28 12:57

一，名词定义割：流网络图G(V,E)的一个划分，记作[S,T]，将点集[V]划分为S和T两部分，且使得s属于S，t属于T，S+TV。最小割：一个网络的最小割也就是该网络中容

一，名词定义割：流网络图G=(V,E)的一个划分，记作[S,T]，将点集[V]划分为S和T两部分，且使得s属于S，t属于T，S+T=V。最小割：一个网络的最小割也就是该网络中容量最小的割。最大流最小割定理：流网络图G=(V,E)的最大流大小等于其最小割容量。
二，存在固定模型的最小割问题构图方法及举例 1-二分图的最小点权覆盖集算法定义：无向二分图G=(V,E)。X，Y分别是这个二分图的两个点集，每一个顶点i都有一个权值vi。选出顶点集合V的一个子集V1使得E中的每一条边都和V1中的点相连(至少有一个端点属于V1)，并且使得V1中所有点的权值之和最小。算法描述：增设源汇点s和t。由s向所有X集合中的点连边，容量为这个点的权值vi。Y集合中的点向t点连边，容量为这个点的权值vi。如果原二分图中u和v之间存在边，则连接u->v容量为正无穷(用来保证这条边不在割中)。对这个图求出最大流的值，既是最小点权覆盖的值。 [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

例题：poj 3308 在一片m*r的区域中存在一些外星人。已知每个外星人的位置，且消灭第i行所有外星人的费用为ri，消灭第j列所以外星人的费用为cj，求最少需要多少费用才能消灭所有外星人。在这里，我们把x轴的所有点看作二分图的一个集合，y轴的所有点看作二分图的另一个集合。如果在第i行j列有外星人，则连接x集合中的i点和y集合中的j点。由此构造出一个二分图。 [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

原问题变成了下面这个问题：给定一个带权二分图G = (V, E)，定义一个点如果被覆盖，那么称所有与这个点相邻的弧被覆盖。求至少去掉多少的点权才能使得所有的点权均被覆盖，也就是最小点权覆盖问题。
例题：poj 2125 给出一个有向图，每次操作都可以移除某个点的所有出边或者所有入边。已知对于每个点移除所有出边的费用和移除所有入边的费用。求至少花费多少可以移除掉图中所有的边。对于这道题，我们把有向图中的每个点拆作u1,u2两个点，其权值分别为拆除其所有出边的花费，拆除其所有入边的花费。若原图有从u到v的边则连u1到v2。构造出二分图后接下来便可以把原题转化为求二分图的最小点权覆盖问题。 2-二分图的最大点权独立集算法定义：无向带权图G的一个点集,使得任何两个在点集中的点在图G中都不相邻且点权和最大。算法描述：Amber大神的论文已经给出证明，最大点权独立集和最小点权覆盖集互为补集，所以最大点权覆盖集的权值和就等于该图的总权值和减去最小覆盖的值。例题：hdoj 1565：给你一个n*n的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。把所有的格子分为两个集合，行数加列数的值对2取模为0的格子以及行数加列数的值对2取模为1的格子。可以看出同一集合内的点是互不相邻的。接下来再把两个集合中互相连接的格子之间连上边。把格子看作二分图中的点，每个点的权值为其所对应的格子的数字大小。原问题便变为从一个带权二分图中取出一些点使得这些点两两不共线，求这些点的权值之和最大是多少。于是便可以通过总权值减去最大覆盖值求解。
3-最大权闭合图定义：在一个有向图中，有边(u,v)，如果选择了u，必须选择v，这样选出的图叫做闭合图。某些点有权值，则选出的权值最大的闭合图，叫做最大权闭合图。 [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

左图中的闭合图有空集,{5},{2,5},{4,5},{2,4,5},{3,4,5},{1,2,3,4,5},{1,2,4,5}。最大权闭合图为{3,4,5}。权值之和为4。算法描述：在原图的基础上增加源点s和汇点t，将原图中的每条有向边替换为容量为正无穷的有向边，s向图中的所有正权点连接有向边，容量为这个点的权值。图中的所有负权点向汇点t连边，容量为这个点权值的绝对值。对构造出的网络图求最小割，用所有正权的总和减去最小割即为最大权值。从s开始进行dfs能访问到的点属于最大权闭合图。（以上图为例，转化为网络流图后的效果如下） [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

具体描述及证明证明详见Amber论文《最小割模型在信息学竞赛中的应用》     例题：poj 2987 一个公司打算解雇一些员工，已知解雇每个人的收益值（可能为负）。解雇某一个人后，他的下属也将被解雇，求最大收益是多少，在取得最大收益时需要解雇多少人。     模版题，按照以上方法建图，求出最大权闭合图权值即可
    例题：zoj 2071 有m个订单，每个订单都能获取一定的收益，但是完成每个订单都需要购买不同的机器，求最多能挣多少钱，需要完成哪些订单，购买哪些机器。     把能获得收益的订单看作正权点，权值为每个订单的收益值。把需要花钱购买的机器看作负权点，权值为-1*价格。每个订单都像其依赖的机器连上有向边。求出这个有向图的最大权闭合图权值即可。
    例题：zoj 2930 有一些任务，每件都需要选择提前完成或者推迟完成，各有不同的花费。给出一系列的依赖关系，也就是如果A推迟完成，则B也必须推迟完成。求出最小花费，以及在这个最小花费的情况下提前完成的任务的数量。     这个题目看似和权闭合图问题没有关系，虽然点与点之间存在依赖关系，但是图中点的权值没有正负之分。我们可以把点的权值设为这个工作提前完成的消耗减去其推迟完成的消耗(可以理解为，如果推迟完成这个任务的话可以比提前完成节约多少钱)，则很明显取出的点权值最大就能保证节约的钱越多。按照推迟完成的依赖关系在点之间连上边，建立有向图，求出闭合图的最大权后用所有任务提前完成需要的花费之和减去这个最大权就是所有任务完成的最小花费。提前完成的任务数量则等于总点数减去从s点能遍历到的点数。
    4-网络流关键割边     定义：关键割边就是增加某条边的容量,可以使得网络的最大流增加。     算法描述：首先对这个网络图跑一遍dinic，得到残余网络。再分别从s和t对残余网络进行dfs。对于一条边(a,b)如果从s可以到达a并且从t可以到达b则该边为关键割边。
    例题：poj 3204 一个由n个点，m条边构成的有向图，每条边都有一定的流量。现在求存在多少条边，在增加这些边的流量后从0点到n-1的总流量会增加。     如上所述，再对原图做过一遍最大流以后分别从源汇点对残余网络dfs即可得到（注：满流的边不一定是关键割边，详见Amber论文）
    例题：zoj 2532 有n个城市，m个中继站，一个总站--0点。有L条有向线路连接这些点，每条线路都有各自的容量。现在所有的城市要向总站发送信号。求增加哪条边的容量可以使得总信号流量增加。     同上面那道题基本相同，在加边时注意增加一个标号即可。         例题：zoj 2587 给出一个网络图和源汇点，判断这个图的最小割是否唯一。     之前做到的题目都是求最小割的大小是多少，这里最小割的唯一性的该如何判断呢。其实这个问题的解决思路和求网络流的关键割边很相似，都是在dinic后再分别从源汇点对这个残余网络进行dfs。如果无法访问到所有的点则说明该图的最小割并不唯一。（我的想法是，如果一个点无法被遍历到，那么他肯定是被夹在两个(或多个)满流的边之间，导致dfs无法到达该点，那么对于这两条满流的边，把任何一个放在割中都可构成最小割，所以推出最小割不唯一）
    5-无向图点连通度(无向图最小点割集)     定义：一个具有N个点的图G中，在去掉任意k-1个顶点后（1<=k<=N）,所得的子图仍然连通，去掉K个顶点后不连通，则称G是K连通图，K称作图G的连通度，记作K（G）。更详细内容请参考：http://blog.sina.com.cn/s/blog_68629c7701010tm5.html     算法描述：因为要对点被删除的次数进行限制，所以把原图中的每个顶点V都拆作网络图中的两个顶点v1和v2。从v1向v2连边，容量为1。代表这个点以及这个点所在的独立轨只能被删除一次。如果在原图中U和V相连，则连接v2->u1，u2->v1,容量为inf，代表这条边可以被经过无数次(对每一对被拆开的点，v2只有一个入度，来自v1；v1只有一个出度，指向v2)。对于给定的S和T，以s2为源点，t1为汇点求出的最大流就使S，T之间不连通至少应该去掉的点数。(下图是把一个四边形拆点构图的例子) [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

    例题：poj 1966 给出一个由n个点，m条边组成的无向图。求最少去掉多少点才能使得图中存在两点，它们之间不连通。
    依次枚举源点和汇点，按照如上方式构图，求出最大流。枚举源汇点得到的最大流最小的值既是这个图的最小点割集。         例题：poj 1815 给出一个无向图，和图中的两个点s，t。求至少去掉几个点后才能使得s和t不连通，并按照字典序输出这些点。     从小到大(因为要按照字典序输出)依次枚举图中除了s,t之外的点，把这个点删去后对这个图做最大流，如果流量减少则说明这个点必然属于一个独立轨，那么就记录这个点，不再还原，并枚举下一个点，否则还原这个点。枚举完成后按顺序输出所有记录到的点即可。
三，网络流(最小割)的灵活运用归类举例     关键词 1-拆点     在部分网络流问题中，有的节点往往包含有限制，从而需要将一些点拆作两个，在它们之间连边，然后把限制分配到这条边的容量上。比如在“无向图的顶点连通度”问题中就需要通过拆点来限制每个点所在的独立轨可以被计数的次数（拆点形成的的边容量都设为1，代表这个点所在的独立轨只能被被计数一次）。
    例题：poj 3498 海上有些冰块，冰块上有些企鹅，现在所有企鹅要聚在一起，由于企鹅跳远距离有限，每个冰块上的企鹅都只能跳到某些临近的冰块上。一个企鹅登陆冰块时，冰块不会受损，但一个企鹅跳离冰块，冰块会受损，受损度为1。给出每个冰块承受的受损度，和附近可以跳的冰块。问所有企鹅最后所在的位置。     这里每个冰块便都有一个限制--可以被跳出的次数。对于每个冰块u，将其拆为u1和u2，连接u1->u2并将这条边的容量设为冰块u可以被跳出的次数。对于两个冰块u和v，如果互相可达，则连接u2->v1，v2->u1，容量都为inf，代表v1和u1都可以被跳入无数次。设一个超级源点s，s向所有拆出的第一个点连边，容量为这个冰块上的初始企鹅的数量。依次枚举拆出的第一个点，将其设为汇点后求网络流，如果最大流等于所有企鹅的数量那么这个冰块就是答案。 [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

<----大致构图
例题：poj 3436 每台电脑有p个组成部分，有n个工厂加工电脑。每个工厂对于进入工厂的半成品的每个组成部分都有要求，由p个数字描述，0代表这个部分不能有，1代表这个部分必须有，2代表这个部分的有无无所谓。每个工厂的产出也不尽相同，也是由p个数字代表，0代表这个部分不存在，1代表这个部分存在。每个工厂都有一个最大加工量。给出这n个工厂的以上数据，求出最多能加工出多少台电脑。这个题目的预处理比较复杂，在这里暂略。预处理的结果就是得到哪些厂可以不用上游工厂供应原料直接自己生产，哪些工厂生产的半成品可以给另一些工厂当原料，哪些工厂出厂的产品直接可以成为成品。在这里每一个工厂都有一个限制，就是其最大加工量。所以我们将每一个工厂都拆作两点，并从第一个点连向第二点，容量为这个最大生产量。如果u工厂的产品可以成为v工厂的原料，则连接u2->v1。如果一个工厂u可以不需要其他工厂提供原料，则连接s->u1容量为inf。如果一个工厂v可以生产成品，则连接v2->t。容量为inf。求出最大流就是答案。 [算法思考]网络流(最小割)问题中的基础构图及分析方法小结（未完……）

大致构图……
    关键词 2-分配     这个问题应该属于网络流问题中涉及题目最多的一个。大致描述一般是有m个容器，n个对象，给出每个容器的容量以及每个对象可以选择的容器，求出是否存在可行的方案能把所有的对象装进容器中或者是否所有容器可以被装满。这种问题建图都很容易，但是常常会伴同floyd，二分，枚举,等等算法同时出现。     通常建图都是从源点向所有对象连边，容量为1，每一个对象都向其可以选择的容器连边，容量是1。每个容器向汇点连边，容量是这个容器最多能容纳对象的数量。
    例题： poj 3189 每头牛对每个牛棚都有一个喜爱值。每个牛棚都有各自的容量。现在要安排这些牛，使得所有牛都有牛棚住，且牛棚中的牛对牛棚的最大喜爱值与最小喜爱值的差值最小。     把牛棚当作容器，牛当作对象，枚举喜爱值的上界与下届，如果某头牛对某个牛棚的喜爱值在这个上下界之间则代表这头牛可以选择这个牛棚，得到所有的可以选择的关系后便按照上面的方式构图，如果求出的最大流等于牛的数量则代表所有的牛都可以找到牛棚。记录在所有符合要求的情况中，上界减去下界的最小值即可。
    例题：poj 1698 有n种工作。每种工作只有在一个星期中的特定几天中才可以干，每天只能干一种工作，每种工作都必须在期限之前干特定数目天。给出n种工作的以上信息，求能否完成所有n个工作。     设源汇点，源点向所有日期连边，容量为1，某个日期如果可以完成某个工作的话则由这个日期向那项工作连边，容量为1，每个工作都向汇点连边，容量为这个工作需要的工作日数量，如果这个图的最大流等于完成所有工作所需要的工作日数量总和则代表这些工作都可以完成。
    关键词 3-二分     经常和网络流，floyd同时出现。一般当题目中出现“最大值最小可以是多少”“最小值最大可以是多少”就应该想到用二分枚举了。大致过程就是不断用二分来枚举一个值或者一个范围，并根据这个范围来修改网络图，求出流量符合题意的情况下枚举的最大值或者最小值便是答案。          例题：poj 2455 给出n个点和m条无向路，每条路都有自己的长度。从1点到n点要走t次两两互不重合的路。求出每条1->n的路中相邻两点最大值的最小值。     应该是最基础的二分加最大流问题了……二分枚举相邻两点之间的距离的最大值mid。在每次枚举中如果某条边的长度大于这个mid则去掉这条边，把所有的边和mid比较过后，对1到n求一遍最大流。如果总流量大于t则说明这个mid符合要求，继续二分枚举，直到找到最小的mid为止。
    例题：poj 2289  n个人分到m个群里面，并规定每个人只能去哪些群，问如何分配才能使这些群中人数的最大值最小，输出这个最小值。     这个……建图就请参考上面说的分配问题的构图吧，这里二分枚举每个群的容量即可。
    例题：poj 2112 K个机器，C个奶牛，他们两两之间的距离由一个邻接矩阵表示（矩阵元素值为0表示这两点间没有直接通路）。每个机器可以容纳M个奶牛。现安排奶牛去机器使得所有奶牛都有机器可以容纳之，所有奶牛中要走路程的最大值最小。     呃……还是参考分配问题的建图。这里枚举的对象是奶牛到机器距离的最大值，对于所有奶牛到机器的距离，如果大于这个值就去掉这条边，如果这个图的最大流等于牛的数量则继续二分枚举，直到找到最小的那个最大值为止。
本文地址：http://t.cn/Sy8YI9 参考文献：《最小割在信息学竞赛中的应用》

推荐阅读

容器
云原生边缘计算之KubeEdge简介及功能特点

本文介绍了云原生边缘计算中的KubeEdge系统，该系统是一个开源系统，用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建，并为网络应用程序提供基础架构支持。同时，KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外，KubeEdge还支持跨平台工作，在私有、公共和混合云中都可以运行。同时，KubeEdge还提供数据管理和数据分析管道引擎的支持。最后，本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]

蜡笔小新 2023-12-14 16:49:01
上传
如何实现织梦DedeCms全站伪静态

本文介绍了如何通过修改织梦DedeCms源代码来实现全站伪静态，以提高管理和SEO效果。全站伪静态可以避免重复URL的问题，同时通过使用mod_rewrite伪静态模块和.htaccess正则表达式，可以更好地适应搜索引擎的需求。文章还提到了一些相关的技术和工具，如Ubuntu、qt编程、tomcat端口、爬虫、php request根目录等。 ... [详细]

蜡笔小新 2023-12-14 19:45:47
php
Monkey《大话移动——Android与iOS应用测试指南》的预购信息发布啦！

Monkey《大话移动——Android与iOS应用测试指南》的预购信息已经发布，可以在京东和当当网进行预购。感谢几位大牛给出的书评，并呼吁大家的支持。明天京东的链接也将发布。 ... [详细]

蜡笔小新 2023-12-14 18:57:09
php
CentOS7.0 U盘刻录工具使用方法详解

本文介绍了使用CentOS7.0 U盘刻录工具进行安装的详细步骤，包括使用USBWriter工具刻录ISO文件到USB驱动器、格式化USB磁盘、设置启动顺序等。通过本文的指导，用户可以轻松地使用U盘安装CentOS7.0操作系统。 ... [详细]

蜡笔小新 2023-12-14 18:55:14
php
GetWindowLong函数

今天在看一个代码里头写了GetWindowLong(hwnd,0)，我当时就有点费解，靠，上网搜索函数原型说明，死活找不到第 ... [详细]

蜡笔小新 2023-12-14 17:58:15
php
EPICS Archiver Appliance存储waveform记录的尝试及资源需求分析

本文介绍了EPICS Archiver Appliance存储waveform记录的尝试过程，并分析了其所需的资源容量。通过解决错误提示和调整内存大小，成功存储了波形数据。然后，讨论了储存环逐束团信号的意义，以及通过记录多圈的束团信号进行参数分析的可能性。波形数据的存储需求巨大，每天需要近250G，一年需要90T。然而，储存环逐束团信号具有重要意义，可以揭示出每个束团的纵向振荡频率和模式。 ... [详细]

蜡笔小新 2023-12-14 17:43:56
nginx
Nginx使用（server参数配置）

本文介绍了Nginx的使用，重点讲解了server参数配置，包括端口号、主机名、根目录等内容。同时，还介绍了Nginx的反向代理功能。 ... [详细]

蜡笔小新 2023-12-14 17:08:34
nginx
【译】发送表单数据

这是原文链接：sendingformdata许多情况下，我们使用表单发送数据到服务器。服务器处理数据并返回响应给用户。这看起来很简单，但是 ... [详细]

蜡笔小新 2023-12-14 16:19:10
nginx
如何去除Win7快捷方式的箭头

本文介绍了如何去除Win7快捷方式的箭头的方法，通过生成一个透明的ico图标并将其命名为Empty.ico，将图标复制到windows目录下，并导入注册表，即可去除箭头。这样做可以改善默认快捷方式的外观，提升桌面整洁度。 ... [详细]

蜡笔小新 2023-12-14 16:17:05
nginx
AJAX的POST请求及实现数据修改功能的方法

本文介绍了使用AJAX的POST请求实现数据修改功能的方法。通过ajax-post技术，可以实现在输入某个id后，通过ajax技术调用post.jsp修改具有该id记录的姓名的值。文章还提到了AJAX的概念和作用，以及使用async参数和open()方法的注意事项。同时强调了不推荐使用async=false的情况，并解释了JavaScript等待服务器响应的机制。 ... [详细]

蜡笔小新 2023-12-14 16:12:01
uuid
数据库的存储结构及其重要性

本文介绍了数据库的存储结构及其重要性，强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离，可以实现对物理存储的重新组织和数据库的迁移，而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构，并介绍了表空间的概念和作用。 ... [详细]

蜡笔小新 2023-12-14 16:00:02
uuid
90后程序员的职业发展之路：从年薪3w到30w的经验分享

本文是一位90后程序员分享的职业发展经验，从年薪3w到30w的薪资增长过程。文章回顾了自己的青春时光，包括与朋友一起玩DOTA的回忆，并附上了一段纪念DOTA青春的视频链接。作者还提到了一些与程序员相关的名词和团队，如Pis、蛛丝马迹、B神、LGD、EHOME等。通过分享自己的经验，作者希望能够给其他程序员提供一些职业发展的思路和启示。 ... [详细]

蜡笔小新 2023-12-14 15:22:09
php
Alink回归预测的不完善问题及期待

本文讨论了Alink回归预测的不完善问题，指出目前主要针对Python做案例，对其他语言支持不足。同时介绍了pom.xml文件的基本结构和使用方法，以及Maven的相关知识。最后，对Alink回归预测的未来发展提出了期待。 ... [详细]

蜡笔小新 2023-12-14 14:25:33
php
Oracle Database 10g许可授予信息及高级功能详解

本文介绍了Oracle Database 10g许可授予信息及其中的高级功能，包括数据库优化数据包、SQL访问指导、SQL优化指导、SQL优化集和重组对象。同时提供了详细说明，指导用户在Oracle Database 10g中如何使用这些功能。 ... [详细]

蜡笔小新 2023-12-14 13:12:10
php
Windows下配置PHP5.6的方法及注意事项

本文介绍了在Windows系统下配置PHP5.6的步骤及注意事项，包括下载PHP5.6、解压并配置IIS、添加模块映射、测试等。同时提供了一些常见问题的解决方法，如下载缺失的msvcr110.dll文件等。通过本文的指导，读者可以轻松地在Windows系统下配置PHP5.6，并解决一些常见的配置问题。 ... [详细]

蜡笔小新 2023-12-14 12:37:25

null5269

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章