基本概念补充：1.网络流可以有环2.网络流中不存在反向边，即若\((u,v)∈E\)，则\((v,u)∉E\)（如果有\((v,u)∈E\)的话，可以添加一个点\(w\)，将\((v,u)\)变成\((v,w),(w,u)\)，所以任意一个有反向边的图都可以转化成没有反向边的图）；这样的话考虑问题更加简便（蓝书的网络流考虑了三条定律，但存在

@目录基础信息引入一些概念基本性质最大流定义Ford–Fulkerson增广Edmons−Karp算法Dinic算法参考文献基础信息引入假定现在有一个无限放水的自来水厂和一个无限收水的小区，他们之间有多条水管和一些节点构成。每一条水管有三个属性：流向，流量，容量。我们用\((u,v)\)表示一条

定义给定一个网络\(G\)，在边集中选择一些边删除使得源点\(S\)与汇点\(T\)不连通。定义删除边\(x\toy\)的代价为\(C_{x\toy}\)，则最小割即即使对于所有的割，删除的边代价最小和。最大流最小割定理内容对于一个网络流图\(G\)，其中有源点\(s\)和汇点\(t\)，那么下面三个

从洛谷搬过来并做了些许润色，后面或许还会增加内容（？第一次学的时候似乎忘记写博客了捏网络流全称网络流理论，是把量类比水流的一种模型。最大流基本芝士对于最大流问题，有一种经典的不能在经典的情景：有一个能生产无限水的自来水厂，若干能承载无线水的节点和家三中节点，点与点之间有

题面传送门感觉网络流学艺不精，被薄纱了/kk原题意是最少一个点的链，在此基础上最少三个点的链，比较难去用网络流考虑。换个思路：先最大匹配出两点链，然后让最多两点链合并上一个单点变成三点链。这样显然单点最少，并且保证了不会有\(3\)个两点链合并成两个三点链，所以这样是符合题目

网络网络和网络流是不一样的。(废话，毕竟他俩差一个字)网络是指一个有向图\(G=(V,E)\)，每条边\((u,v)\inE\)都有一个权值\(c(u,v)\)，我们把它叫做这条边的容量。显然，当\((u,v)\notinE\)时，\(c(u,v)=0\)。其中有\(2\)个特殊的点：源点\(s\)和汇点\(t\)，\(s,t

网络流和最大流问题1网络流和最大流问题阐述网络流基本概念网络流图中，从源点出发，在满足每条边容量限制的条件下，汇点t最多能接收多少流量s:sourcet:target网络流需要满足的限制容量限制平衡限制：除了源点s和汇点t，对于每一个点，流入量等于流出量从源点s流出的流量，一定

网络流定义参见\(OI\Wiki\)。最大流算法定义：最大的可行流。思想：建出原图的残量网络，不断在残量网络上尝试进行增广，最后若没有可增广的路径则求得最大流。一种可以求得最大流的算法：Dinic求出残量网络\(G\)以\(S\)为源点的分层图\(L\)。使用DFS算法搜索原图

一、亿些小定义网络：是一张图\(G=(V,E)\)，每一条边\((u,v)\)都有容量限制\(c(u,v)\)，其流量为\(f(u,v)\)。定义流量函数为\(f:V\timesV\to\mathbb{R}\)，是点集中二

Wikipedia上关于Ford-Fulkerson算法的描述如下AlgorithmFord-FulkersonInputsGraphwithflowcapacity,asourcenode,andasinknodeOutputAflow

之前网络流都是背板子和结论的，现在试图严谨地写一篇关于网络流的笔记。网络流东西很多，一下子肯定总结不完，所以咕计是个咕咕项目。@目录一、最大流简介和引入Ford-Fulkers