个人网络流知识小结

第一篇：个人网络流知识小结

个人网络流知识小结好啊，入门资料，包括简单介绍网络流的知识概念以及Dinic的算法介绍，主要思想就是bfs进行分层，在dfs找增广路径，以及ISAP算法介绍，很全了

HDU3549 最简单的网络流入门题，poj1273 先是写了最基础的 Edmonds-karp(EK)算法，时间复杂度为O(VE2)有邻接矩阵的实现，还有邻接边的实现，后者容易出错！编程复杂度加大，不过效率较矩阵高

对于EK算法与ISAP算法的区别：

EK算法每次都要重新寻找增广路，寻找过程只受残余网络的影响，如果改变残余网络，则增广路的寻找也会随之改变；SAP算法预处理出了增广路的寻找大致路径，若中途改变残余网络，则此算法将重新进行。EK处理在运算过程中需要不断加边的最大流比SAP更有优势

3.Dinic算法 O(v2E)代码分别有递归的实现，和非递归的实现版本

算法思想主要如下：

1.初始化流量，计算出剩余图

2.根据剩余图，计算层次图，如果汇点不在层次图中，那么算法结束

3.在层次图内不断用bfs增广，直到层次图内没有增广路为止

转2

4.ISAP算法，别人写的很好，理解了，直接摘抄了，引用http:///?p=34 众所周知，在网络流的世界里，存在2类截然不同的求解思想，就是比较著名的预流推进与增广路，两者都需要反向边的小技巧。

其中预流推进的算法思想是以边为单元进行推流操作。具体流程如下:置初始点邻接边满流并用一次反

向bfs对每个结点计算反向距离标号，定义除汇点外存量大于出量的结点为活动结点，每次对活动结点按允许边（u->v:d[u]=d[v]+1）进行推流操作，直到无法推流或者该点存量为0，若u点此时仍为活动结点，则进行重标号，使之等于原图中进行推操作后的邻接结点的最小标号+1，并将u点入队。当队列为空时，算法结束，只有s点和t点存量非0，网络中各顶点无存量，无法找到增广路继续增广，则t点存量为最大流。

而增广路的思想在于每次从源点搜索出一条前往汇点的增广路，并改变路上的边权，直到无法再进行增广，此时汇点的增广量即为最大流。两者最后的理论基础依然是增广路定理，而在理论复杂度上预流推进要显得比较优秀。其中的HLPP高标预流推进的理论复杂度已经达到了另人发指的O（sqrt(m)*n*n），但是其编程复杂度也是同样的令人发指--

于是我们能否在编程复杂度和算法复杂度上找到一个平衡呢，答案是肯定的。我们使用增广路的思想，而且必须进行优化。因为原始的增广路算法（例如EK）是非常悲剧的。于是有人注意到了预流推进中的标号法，在增广路算法中引入允许弧概念，每次反搜残留网络得到结点标号，在正向增广中利用递归进行连续增广，于是产生了基于分层图的Dinic算法。一些人更不满足于常规Dinic所带来的提升，进而加入了多路分流增广的概念，即对同一顶点的流量，分多路同时推进，再加上比较复杂的手工递归，使得Dinic已经满足大部分题目的需要。

然而这样做就是增广路算法优化的极限么？答案永远是不。人们在Dinic中只类比了预流推进的标号技术，而重标号操作却没有发挥得淋漓尽致。于是人们在Dinic的基础上重新引入了重标号的概念，使得算法无须在每次增广后再进行BFS每个顶点进行距离标号，这种主动标号技术使得修正后算法的速度有了不少提高。但这点提高是不足称道的，人们又发现当某个标号的值没有对应的顶点后，即增广路被截断了，于是算法便可以提前结束，这种启发式的优化称为Gap优化。最后人们结合了连续增广，分层图，多路增广，Gap优化，主动标号等穷凶极恶的优化，更甚者在此之上狂搞个手动递归，于是产生了增广路算法的高效算法–ISAP算法。

虽然ISAP算法的理论复杂度仍然不可超越高标预流推进，但其编程复杂度已经简化到发指，如此优化，加上不逊于Dinic的速率（在效率上手工Dinic有时甚至不如递归ISAP），我们没有不选择它的理由。

5.自己的理解

不管怎样，普通的EK一般来说 复杂度是在O(n*m*m)的，而Dinic和ISAP都是O(n*n*m)d的，而ISAP的几个优化，有将效率进一步提升，关于复杂度的分析，算法导论有介绍，主要是理解下后面的分层思想和预留推进思想，以及根据dfs回朔来判断是否可以推进流还是做重标记等，这里可以用ISAP算法和DInic算法，其中主要难点是在网络流的建模上！邻接表的建立也有许多巧妙之处，仅仅是数据结构上的邻接表，效率和空间浪费的简直令人发指！

接下来就是深入的部分，可以看得资料和论文如下：

很好，很全面的学习资料和总结题集《Network Flows-Theory, Algorithms, And Applications》

《Combinatorial optimization:networks and matroids》

解决网络流的几种方案在这里，非常清楚

http://dantvt.is-programmer.com/tag/Dinic

/Files/panzhizhou/国家集训队论文网络流整理.zip

第二篇：网络编码知识小结

注：本小结报告来自两份论文

[1]上角标1代表 论文 <网络编码的研究进展> 杨林 郑刚等

[2]上角标2代表 论文 <网络编码研究综述> 陶少国等

网络编码研究综述

万里 基本概念

起源：R.Alshwede的蝴蝶网络模型定义：网络编码是一种融合编码和路由的信息交换技术，在传统存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码信息融合，增加单次传输的信息量，提高网络整体性[1]能。

[1]本质：利用节点的计算能力提高链路带宽的利用率。核心思想：具备编码条件的网络节点对接收到的信息进行编码，然后传输给下一级的网络节点，收到信息的下一级节点如果具备编码条件，又对其接受的信息按照同样的方式进行传输与处理，如此反复，直到所有经过处理后的信息汇聚到信宿节点为止。最后，在信宿节点，[2]通过译码，即可译出信源发送的原始信息。主要优缺点： 优点： 提升网络吞吐量 2 均衡网络负载

从作者的例子[Fig.2]可以看出，虽然传输链路增加了，但是每条链路上传输的信息更均衡，解决了网络拥塞问题。3 提高带宽利用率

同2，虽然传输链路增多了，但是每条链路上的信息减少了（均衡了），总体是减少了网络带宽，提高了网络带宽利用率。缺点：

虽然网络编码优点突出, 但运用网络编码增加了计算的复杂性, 而且网路节点需要缓存足够的输入信息, 因此编码操作增加了传输时延和节点的额外的I/ O、CPU消耗。统计数据表明, 即使应用最有效的随机网络编码，其编码和译码的时间也不容忽视。此外, 应用网络编码还存在同步问题, 这主要是由于信宿节点必须等待收到足够的编码信息, 才能开始

[2]译码。同步问题给在实时系统中应用网络编码提出了挑战。

[2] 2 原理与数学模型

2.1网络编码分类

网络编码按照节点输出和输入的关系可划分为线性网络编码和非线性网络编码 网络编码按照编码系数生成的随机性可划分为随机网络编码和确定性网络编码（通过算[1] 法算出系数）2.2线性网络编码

目前的网络编码研究均局限于有限域中的线性网络编码。2.3几个基本概念 信息流：信源发送的信息，链路传输的信息以及信宿接收到的信息，均以向量形式取

[2]之于有限域。称其为信息流。本地编码向量:将节点上的信息流作为节点输入链路上传输信息的线性组合。[链路的消息流与输入链路的消息流的映射关系] 3 全局编码向量:将信源发送信息表示成信息流向量，将链路上传输的信息流当做信源向量的信息流向量各元素的线性组合，该线性组合系数构成的向量就是该链路的全局编码向量。[链路的消息流与信源的信息流的映射关系] 备注：如果忘记 可以参考论文2中的Fig.3 2.4数学模型

[2] 3网络编码的构造方法

网络编码的KEY：求得每条链路对应的编码向量 3.1集中式编码方法 3.1.1 指数时间算法

设N1,N2,...,Nn表示所有编码链路对应的编码向量, 则必定存在函数关系: p = f(N1,N2,..,Nn),并称使p=0的点(N1,N2 , ⋯,Nn)的集合称为被“函数p 分割出来的代数簇”,[2]因而算法的目标就是求得一个不位于“函数p分割出来的代数簇”上的点(p0)。3.1.2 多项式时间算法

3.1.3其他算法 1引入通用LCM（贪婪算法与启发式算法）可实现多速率的网络编码

但是由于计算量大，实现过程复杂，不实用（作为多速率网络编码的探索，具有很重要的意义）

2线性多播、线性广播和线性扩散：线性扩散是线性广播的特例, 线性广播是线性多播的特例, 反之不成立.线性广播说明了通过增加信源发送的信息流向量的维数, 可以提升传输

[2]速率;线性扩散能保证信源节点以互补的形式发送信息流。

[1]3冲突图法、矩阵满秩法、图染色法等几种构造方法。3.2分布式编码方法 3.2.1确定系数构造法

其核心思想是将网络拓扑分解成多个子树，并保证每个子树的编码矢量属于其父树编码

[1]矢量的扩张空间，且任意两个子树的共有信宿的编码矢量均线性无关。3.2.2随机系数网络编码

随机网络编码(简称RNC),该方法基于一种随机选择编码向量的策略:对于除了信宿节点外的所有中间节点,只要在一个足够大的有限域上随机选择它们输入链路到输出链路的映射,而且各节点映射关系的选取是相互独立的,就能以较高概率使各个信宿节点对应的系统转移矩阵满秩,即各信宿节点能以较高的概率成功译码。与时间多项式算法总能保证成功译码不同, 在RNC 中,虽然不能确保最终形成的系统转移矩阵M满秩, 但由于是随机选择编码向量, 其复杂性与确定性算法相比要低得多, 更易于实现, 而且99%以上的译码成功率在一般情况也足以满足需求.因此,随机网络编码具有重要的理论价值和应用价值，得到了广泛的关注和

[2]应用, 如微软提出的P2P文件共享系统Avalanche便是基于RNC的典型应用。3.3集中式与分布式的比较

集中式：需要了解全局拓扑以分配编码系数，可扩展性差。

确定分布式：掌握局部拓扑即可对入编信息进行编码，但需要通信开销。

[1]随机网络编码：实用性强，需要较大的字母表，存在解码失败概率。

4性能参考以及优化

网络编码的主要性能指标包括字母表、编解码速度和编码增益等．其中，字母表是最重要的性能指标，决定了网络编码解的存在性、编解码复杂度、延时以及存储开销．编解码速度反映了编解码操作的计算复杂度．编码增益则表征网络带宽的利用效率．网络编码设计的一个重要目标就是尽可能使用小的字母表和低复杂度的编解码操作来提高网络吞吐量或减[1]小延时．

4.1网络编码复杂性的影响因素分析 4.1.1编码构造方法

网络编码的核心，目标是寻找复杂性低的算法（分布式与集中式的共同目标）。4.1.2编码操作数

可从三个角度分析：信息分组、编码链路和编码节点, 其中从信息分组的角度减少其操作数目是降低编码操作复杂性最理想的方式, 但是分析的难度较大, 一般均从减少编码链

[2]路或者节点的数目来考虑。4.1.3有限域的大小

保证足够的译码成功率的前提下（有限域过小，译码成功率降低）, 应尽量减少有限域的大小。

4.2基于简单网络的解决方案

将普通网络转化为某种易于表达, 且各网络节点具有共同特征的“简单网络”将普通网络转化为简单网络, 其网络拓扑变得十分简单,但一个不容忽视的问题就是: 简单网络的规模(节点数)比原普通网络却膨胀了许多, 也就是说网络编码的代价被放大了,“简单网络”的最小代价并不等于原网络的最小代价.但是, 将网络“简化”处理的思想在方法论上具有

[2]重要的借鉴意义,为最小代价的网络编码提供了研究方向。4.3基于信息流

信息流分解的基本原理是按照网络中信息流的特征和共性, 将原网络节点划分为一系列的子树图, 这些子树图中的节点拥有相同的编码向量, 子树里面的节点的拓扑结构不影

[2]响整个系统的多播传输, 因此每个子树可以当作一个节点来处理。4.4基于最小代价函数的解决方案

借鉴路由多播的最小代价树，将网络编码转化为线性规划问题。

5应用与研究趋势

5.1应用领域

[1]Ad Hoe网络、传感器网络、P2P内容分发、分布式文件存储和网络安全等领域。

[2]无线网络、应用层多播和P2P文件共享、传输的差错控制。5.2研究趋势

5.2.1多源网络编码

对于信源数目大于2的网络编码多播，研究不够充分，但多源多播广泛存在。5.2.2非组播网络

对于非组播网络的网络编码理论研究。5.2.3非线性网络编码

非线性研究尚未起步，性能还不可知，比线性网络编码要求与难度更高。5.2.4具体实现

网络编码的具体实现需要考虑诸多因素，也是有意义的研究方向。5.2.5与其他领域的融合

与信源编码的联合设计与优化、与信道编码和调制技术的结合、与多描述分层编码的结合。

5.2.6降低网络编码复杂度

降低网络编码复杂度，实现最小代价网络编码。5.2.7安全方面

无线网络编码在安全方面的研究。

第三篇：甲流小结

幼儿园甲型流感防控工作督导检查小结

为了认真落实甲型流感防治工作，保障广大人民群众的身体健康，根据《甲型流感诊疗指南》，结合上级卫生行政部门指示，按照“托幼机构（小学）甲型流感防治措施要点”和责任状的规定，我站成立了托幼机构甲型流感防控工作督导检查小组，对本区范围内的一所托幼机构和小学进行了分包负责，每处由两名防疫人员负责进行督导检查，本周进行了 2 次督导检查，发现问题并提出了整改意见，做好了督导记录，并保存备查。现对本周督导检查情况做小结如下：

一、托幼机构

在对幼儿园检查工作中，发现该幼儿园主要存在以下问题：

1、幼儿园儿童一部分儿童由学校班车接送，班车坐垫未每天更换。

2、大型玩具未消毒。

3、流动洗手无充足水源。

4、教室未进行定期消毒。

针对以上问题提出了整改意见，班车坐垫要每天更换，改善寝室条件，做好各项消毒工作，及时做好记录。

二、小学

在对小学检查工作中，发现该学校主要存在以下问题：

1、学校班车坐垫未每天更换，消毒记录不完整。

2、班级晨检流于形式。

针对以上问题提出了整改意见，要求其认真做好班车消毒并留有记录，坐垫要每天更换。加强晨午检和班级消毒工作，做好记录。

在本周的督导检查中，未发现我区有患甲型流感儿童。

第四篇：网络安全问题---个人小结

网络安全问题-----个人小结

随着互联网事业的飞速发展,精彩的网络世界不可阻挡地走进了我们的生活。计算机互联网作为开放式信息传播和交流工具，已经走进了我们的生活。互联网的发展一方面为我们的学习、交流以及娱乐提供了更为宽广的天地，但是另一方面，由于互联网资源鱼龙混杂、良莠不齐，致使缺乏自律能力的同学通宵达旦沉湎其中，对学业、健康和思想都造成了巨大的危害。所以,对于未成年人来说，互联网是一把锋利的“双刃剑”。

积极作用：

1、快速掌握多方面知识的重要途径

网络已经成为一种获取知识的重要来源。全世界各大图书馆的资料大多可以通过网络获得，它不仅快捷而且也省去了大量的额外的花销。网上还有新闻，资料，经济，娱乐，文学等各种信息。在网上，中学生可以看到最新，最快，最权威的新闻，可以学到书本上没有的知识，了解到更广泛的未知信息，也使更多的学生更快、更早、更接近科技前沿，使我们更加的热爱科学，祟尚科学。

2、接受教育的有效方式

据了解，有许多学生喜欢“网校”这种新式的教学方式，“网校”里老师单个教你，“同学”们在交流中互相学习，完全没有在教室里与老师面对面的那种拘束，对中学生的自由发挥有很大的帮助。

3、网络是加强交流的有益工具。

4、上网的学生有许多去过聊天室或QQ等其它的交流网站，虚拟的世界里，各自谈论着自己喜欢的话题，网友不论老少，不论职业，只要认为兴趣相投就可以尽吐心声。这对渴求朋友，渴求友谊，渴求倾诉的我们是一个绝好的机会。我们在网络中愉快地畅谈，得到心灵上的放松和解脱。

消极作用:

1、上网聊天时，由于中学生的自身特点：对社会的认识不深，不能正确的对待社会上的不良现象，自控能力差，对一些不健康的东西容易上瘾，从而影响自己的情绪，往往会带到现实生活中。这里有一个很好的例子，2月27日中央电视台焦点访谈播出了新疆经济电视台对北京等各大城市网吧的调查，其中北京某高校附近许多大大小小的网吧形成了网吧一条街，在每天8—9点，网吧就爆满了，上网的大部分是大学生和高中生，绝大多数上网是玩游戏，聊天，容流量大，门外总有人在等待。许多中学生一坐就是几个小时，有的一连几天都不回家，一天24小时连轴转，在网吧里吃住，有的家长一连几天都找不到自己的孩子，网络的诱惑使许多中学生沉溺其中。

2、由于上网时间长，容易造成对身体的损害。过度沉溺于电脑网络中对身体也是一种损害，上网时在电脑前一坐就是几个小时，只有手指在不停地点，目不转睛地盯着屏幕，对身体健康也是很大伤害的，尤其；是对眼睛的危害，现在我国中学生原近视率已达65％，而且有逐年上升的趋势，所以整天沉溺与网络是不可取的，有时上网的愉悦是以金钱和自己身体的健康为代价的。聊天、游戏、造成了学生成绩下降，身心健康受到伤害，不利与中学生的健康成长。

我们要遵守公约，争做网络道德的规范。我们要学习网络道德规范，懂得基本的对与错、是与非，增强网络道德意识，分清网上善恶美丑的界限，激发对美好的网络生活的向往和追求，形成良好的网络道德行为规范。

我们要遵守公约，争做网络文明的使者。我们要认识网络文明的内涵，懂得崇尚科学、追求真知的道理，增强网络文明意识，使用网络文明的语言，在无限宽广的网络天地里倡导文明新风，营造健康的网络道德环境。

我们要遵守公约，争做网络安全的卫士。我们要了解网络安全的重要性，合法、合理地使用网络的资源，增强网络安全意识，监督和防范不安全的隐患，维护正常的网络运行秩序，促进网络的健康发展。

网络在我们面前展示了一幅全新的生活画面，同时，美好的网络生活也需要我们用自己的美德和文明共同创造。让我们认真贯彻《公民道德建设实施纲要》的要求，响应全国青少年网络文明公约的号召，从我做起，从现在做起，自尊、自律，上文明网，文明上网，做一个“文明的网络人”。

第五篇：网络流构图总结

网络流专题研究

福州一中 肖汉骏

预备知识(参见Amber论文)网络和流

残留网络和增广路径 最大流和最小割

主要算法

最大流

增广路方法 Ford-Fulkerson method 一般增广路算法 Labeling algorithm 连续增广路算法

由陈启峰提出，竞赛中相当实用，近于O(m)容量缩放增广路算法 Capacity scaling algorithm 最短增广路算法 Edmonds-Karp algorithm 连续最短增广路算法 Successive shortest augmenting path algorithm(Dinic augorithm)预流推进方法Preflow-push method 一般预流推进算法 Generic preflow-push algorithm 先进先出预流推进算法 FIFO preflow-push algorithm 最高标号预流推进算法 Highest-label preflow-push algorithm(Relabel-to-Front algorithm)最小费用流

最小费用路方法

一般最小费用路算法(SPFA找增广路，复杂度近于O(mf)，竞赛中实用)注意：初始流的费用必须保证是在所有同流量流中最小的。原始-对偶算法

消圈方法

一般消圈算法 网络单纯形法

常见变形

多源多汇问题

可通过增添超级源和超级汇解决。

点有容量或费用

可以尝试拆一个点为一入点一出点，将点的限制转移到入点到出点的边上。

重边、无向边和自环的处理

对于使用边链表存储的图，重边一般不需要特殊处理。但当重边的数量太多以至于显著影响算法效率时，可以考虑将相同起点终点的边的容量相加。

而无向边则可以看做是在两个方向上都只要求Flow小于Capa即可。而最小费用流问题中的重边却反而成为一种处理复杂权函数的手段。根据题目要求或者问题性质，可以为重边列出一个费用随流量变化的函数。如果将这个函数的离散点顺次相连，得到的是若干斜率不断增大的折线段，则可为每段折线段建立一条边，根据最小费用流的性质，重边选择的必然是连续的一段。

给定流值的情况

可以增设一个源，向原来的源连一条容量为给定流值的边。

或者在每次增广的时候，直接将源的可改进量设为到给定流值的差。

或在回溯增广的时候，将路径的增广量同到给定流值的差比较后取小。

有上下界的流问题

注意到下界必须被满足，可以将所有必要弧抽取，经过新建的源和汇。但这时必须为原来的汇到源增添一条容量为无穷大的边，使之成为满足流量平衡条件的普通节点(注意，汇到源的流量实际上就是原网络的流值)。再运行最大流算法得到一个可行流。

另一方面，可以先满足下界，此时有一些点不满足流量平衡条件。而这可以用多源多汇问题解决。

若求的是最大流，则可以在可行流的基础上进行增广。

如果求的是最小可行流，则可以通过交换源汇，去除新增的点和边后运行最大流，将多余的流抵消。也可以通过二分汇到源的容量，运行可行流。

最大费用流

将费用取负，运行最小费用流算法。或将SPFA的大于号反向。

可行最小费用流

从T向S连边，在这基础上找负权圈增广。分离必要弧，使用最小费用流进行增广。

单位容量网络流

在构图上，可以利用只有两种取值的特殊性，容量用true和false表1和0，流量用true表1或-1，用false表0。则可以增广当且仅当xor的结果为true，增广可以直接变为相反的布尔常量。

而单位容量网络的另一个重要性质是增广次数不超过N次。则一般增广路算法的增广次数得以改进。

动态流

可以对时间拆点，建立层次图处理。

几个构图的思考方向

流表方案

【例1】 奶牛的新年晚会《算法艺术与信息学竞赛》p315 注意到奶牛和食物具备“会做”这样的关系，且其选择也只有做1盘与不做两种。而对每头奶牛有盘数限制k，对每种食物也有相应的上限值。则二分图模型呼之欲出。

【例2】 圆桌吃饭问题《算法艺术与信息学竞赛》p319 注意到幼儿园和桌子有“派出小朋友入座”这样的关系，且其选择也只有派1个与不派两种。而对幼儿园的人数和桌子的人数都有上限值。则也可很容易想到二分图模型。

【例3】 赛车问题 [2002][金恺]网络流应用

注意到两人的赛车均有上场次数的限制。而每次比赛均是某两辆车的对决。则就可以建立二分图模型，利用网络流解决。

【例4】 混合图的欧拉回路《算法艺术与信息学竞赛》p324 注意到边和点具有“为点增加入度”的关系，可以首先统计出每个顶点需要的入度，然后为每个点和边给出容量限制。

另外一种方法是对混合图任意定向，然后统计需要反向的边的个数。反向边对于原起点来说增加了入度，对原终点来说了减少入度。如果某点的入度要增加，则可从源向它连边；如果入度需要减少，则可以向汇连边。最后只要检查所有从s出发或到达t的边是否全部满载。

注意到在这种二分图上的增广实际上在对应的原图中就是找一条路径，使得头尾顶点都被改进。这便是一种调整思想。

【例5】 取整矩阵 Yali Train Day12 注意到每个元素只有取下整和取上整两种选择，而每行每列对相应元素取上整的次数有上下界。则可以通过求有上下界的最大流解决。

而另一种思想是随机确定是取上整还是取下整，再根据要求进行调整。每次先试图找一个行列的优化方向一致的格子进行优化。再试图找一个不满足条件的格子，将数值移动到同行/同列的格子中。【例6】 矩阵 CTSC2007 注意到b非0即1。而每行每列对相应元素取1的次数有上下界，则可以通过求有上下界的最大流解决。

而另一种思想是随机确定是取上整还是取下整，再根据要求进行调整。每次先试图找一个行列的优化方向一致的格子进行优化。再试图找一个不满足条件的格子，将数值移动到同行/同列的格子中。

这实际上就是利用了增广过程在原问题中的映射。

【例7】 列车调度 [2002][金恺]网络流应用

本题每辆列车只能进出站一次，而一旦选择某辆列车，下一辆可选列车也被确定。此时的一个单位流对应的应该是一个车道。而点有容量则可以利用拆点法。于是便要解决一个最小费用流问题。

【例8】 餐厅问题 [2002][金恺]网络流应用

本题每天都有对毛巾的需求，而毛巾的来源有多种，去向也有多种，则可以考虑对每天进行拆点。此时的一个单位流对应的是一条毛巾，由于每天的弧必须被满足，则是一个有上下界的可行费用流问题。

也可以重新构图，直接利用最小费用最大流解决。

还可以根据增广的特殊性，贪心解决。

常用技巧

注意处理对象以及对象间的关系。如例1和例2，都提供了3个对象，要仔细分析具体的限制在哪些对象上，什么对象将另两个串联起来。

注意分析对象身上的限制，可能有多种变形，比如单纯的上限，又或是上下界均有。但共同点是相连的边在两个对象的计算方式都是一样的。比如例1中对盘数的统计，例2中对人数的统计，是平权的。挖掘出平权的计数关系，容易分析出什么是点，什么是边。

割表方案(可参见Amber论文)【例1】 最大密度子图

结合01分数规划的一般做法，对答案进行猜测，转而求解一个最大化问题。

【例2】 最大获利 NOI2006 首先可以将边变为点，利用割所具有的性质，将边点依赖关系用容量为正无穷的边表示。然后利用最小割这个优化工具，从问题反面考虑，计算最小代价。

更优的办法是Amber提出的。注意到边权非负，则可以贪心地选择点导出子图。而点导出子图的权和不方便计算，可从反面考虑，用S集中的总边权和减去割表示。为了利用最小割这个优化工具，将每个点连到汇的代价设为选入S集中的代价，为建设费用，连到源的代价设为选入T集中的代价，为总边权和。而原图的边容量可直接设为边权。

【例3】 最优压缩 Yali Train Day4 注意到每个元素只有V0和V1两种选择，而权的计算实际上对应于点的变化以及边的变化。也就是只有V0与V1之间的边才计入代价。则容易想到割，并用与源和汇有关的边容量处理点权。

常用技巧

1.2.3.4.不连通。任意一条s-u-v-t路径都会被割截断。两类点。将xor操作变为割。

用正无穷容量排除不参与决策的边。

利用与源和汇有关的边容量处理点权。连到汇的容量设为选入S集中的代价，连到源的容量设为选入T集中的代价。5.反向思考，充分利用最小割这个优化工具。

其他

1.对时间的处理。可以考虑拆点，建立分层图解决。

2.矩阵类型的题目常常用二分图进行构图。这是由行列以及元素的天然关系决定的，限制在行列上，由元素将其联系在一起。有时也使用奇偶染色构图，此时相邻关系是考察重点。有的还要进行离散化，例如有障碍棋盘上互不攻击的车的个数，就是先对连续空白段进行离散化而得的。

利用特殊性进行增广

【例1】 二分图匹配问题

由于二分图匹配问题均是单位流量，且连边方式十分特殊，可以只存储Y部节点的匹配情况，利用CQF式的网络流进行优化。速度非常可观。

【例2】 剪刀石头布 WC2007 首先进行问题转化：注意到剪刀石头布情况实际上对应一个长度为3的环。而非剪刀石头布情况这对应一个拓扑的环，其中有一个顶点有两条出边，另一个顶点有两条入边。则要求剪刀石头布情况尽量多，就是要求顶点的入边平方和尽量小。

于是可以为尚未确定的边建立节点，如果边点存在邻接关系，则连接一条边。点的权可以用到汇的边上的费用来表示，实际上是一个凸函数。这就可以利用重边的手段处理了。观察本网络的增广过程，相当于选取一条路径，将其反向，如果解更优的话则保留改动。这也就是调整法的一种实现了。

【例3】 数据备份 APIO2007 首先可以证明选择的必然是k条边数为1的线段，而要求权和最小。这显然是一个最小费用最大流问题。但本题数据规模极大，必须另找方法。

注意到每次进行增广的时候，或者是直接添加一条长度为1的线段。或是将连续交错的线段全部反向，则一旦形成连续交错线段，就不会改变。

这可以使用映射堆进行优化。每次删除一个权最小的线段，并将前后线段删除，把当前线段的权修改为前后线段的和减去当前线段的权即可。

其他

对于一些有向图的问题，由于增广路的特殊性，调整方法往往是对一条链反向。分析时可以紧抓入度或紧抓出度，结合一起分析反而增大难度。

对每个元素有两种选择的问题，可以尝试任意选择一种，再根据限制进行构图。