网络流

无源汇有上下界网络流

模型:一个网络,求出一个流,使得每条边的流量必须>=Li且<=Hi,
每个点必须满足总流入量=总流出量(流量守恒)(这个流的特点是循环往复,无始无终)

有源汇上下界最大流

求一边可行流后在残余网络上原先源汇

路径覆盖

DAG图最小路径覆盖
最小不相交路径覆：

把原图的每个点V拆成$VxVx和VyVy$两个点，如果有一条有向边A->B，那么就加边$Ax−>ByAx−>By$。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

证明：

一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

最小可相交路径覆盖：

floyed求出传递闭包后建二分图，就变成了最小不想交路径

证明：

为了连通两个点，某条路径可能经过其它路径的中间点。比如1->3->4，2->4->5。但是如果两个点a和b是连通的，只不过中间需要经过其它的点，那么可以在这两个点之间加边，那么a就可以直达b，不必经过中点的，那么就转化成了最小不相交路径覆盖。
法2：拆点限流，上下界[1,1]，源点向每个点练边，每个点向汇点练边，那么最小流就是答案

ps：每条增广为一条覆盖链

Dilworth定理

对于DAG：x可达y是一个偏序关系，否则不是

偏序：

1.自反性
2.反对称性
3.传递性

定理1，

令$（X,\leq）$是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
定理2)
令$（X,\leq）$是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

即：

链的最少划分数 = 反链的最长长度

状态分层

把每种分层建图----->有时间ixnazhi-------->按时间分层
例题：

最大权闭合子图

hall定理