对网络流的一个小总结

关于网络流的复杂度 一般数据范围低于1k就可能考虑网络流

拆点的技巧

拆点可以限制一条边的流量
一条边连向另一条边 出点---->入点

最大流

我的选择是用 dinic

最小割

1最大全闭合子图 如果两个东西 （选这个必须选另一个） 那么我们可以 转化为最小割
然后dfs去跑 方案
2限制同时选
3限制同时不选
（最小割真的很妙 也很难 真的很考验思维）

最小割的必经边 首先都是要跑 一遍最小割（最大流等于最小割）
最小割的可行边 跑一遍最小割

费用流

最小费用最大流
最大费用最大流
本质是最短路去找一条增广路 但是我们考虑到有负权 （有环的我们另行考虑，下面有解释） 
我们选择用spfa 优化   
1
2
3
4

上下界网络流

  最主要的思想：
  ru ++    chu  --     >0 有多余 向超级汇点连边     <0  超级源点向这个点连边 做一个供给的效果 
    
1
2
3

最小费用循环流

经典例题 就是 网络流24题的 餐巾计划问题 我们需要让某条边数流满 而不直接求
如果有负权环的费用流 本质的处理是 把他的负数边留满 那么我们可以向他的 反向边 连 c -inf 的流量
保证它流满

关于二分图

最小点覆盖 最大匹配
最小边覆盖 顶点数-最大匹配数
最大权独立集 顶点数-最大匹配数
最少路径点覆盖 顶点数-最大匹配数
最小路径可重复路径点覆盖 顶点数-传递闭包的最大匹配数
最长反链 =最小可重复路径点覆盖 （比较不常见）
最大团等于补集的 最大全独立集
二分图完备匹配的必经点 可以dfs
二分图完备匹配的必经边 如果满流 正向连边 不在完备匹配的边 反向连边 跑有向图 tarjan

一些新颖的建边技巧 （hard）

差分建边

最小割树 （我们可以询问任意两个点的 最小割） lca处理

我们可以分治处理
然后倍增查询

  void build(int l,int r)
    {
        if(l>=r) return;
        int x=pdx[l],y=pdx[l+1];
        int cut=Dinic(x,y);
        now++;dfs(x);int p=l,q=r;
        for(int i=l;i<=r;i++)
            if(col[pdx[i]]==now) tdx[p++]=pdx[i];
            else tdx[q--]=pdx[i];
        for(int i=l;i<=r;i++) pdx[i]=tdx[i];
        add_edge(x,y,cut);
        add_edge(y,x,cut);
        build(l,p-1);build(q+1,r);
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

全局最小割 待补

最大密度子图 待补 （不会，待补）

--------------

 可结合二分答案 也是比较经典了
 会有线段树建图   
 可以结合树连剖分（代码hard）
1
2
3