【最大流】Dinic

★推荐：。

本质：网络流本质上是为了解决一类取舍问题，这类取舍问题无法得知最优策略的模式（无法DP），因此通过构造一些带容量的路径表示原题目容量，模拟水流在这些容量之间的取舍，从而可以利用网络流来解决取舍问题。

Dinic算法：bfs得到分层图，然后严格按照分层图寻找增广路，重复至S-T断路。

当前弧优化：DFS过程中访问x点时一旦流入量=流出量就退出，记录下此时正在考虑的弧（当前弧），下次从此处继续考虑即可。

当前弧之前的弧，不能使流入量-流出量=0，那么一定该弧以及该弧之后的弧中有断裂，那么下次再考虑就没有意义了。

当前弧本身，使流入量-流出量=0，也就是使该点前面的弧中最小的一条断裂了，当前弧以及当前弧连出去之后的弧只是有可能断裂，那么下次就应该从这条当前弧开始考虑。

写Dinic一定要加当前弧优化，效果显著。

反向弧：大多数时候反向弧并不影响算法正确性，所以不要考虑以免造成混乱。

反向弧的意义推荐。

反向弧就是给程序提供反悔的机会，流过反向弧x'相当于帮原来的x流完剩余的路程，而让x不流过来改去别的地方。

复杂度：O(n^2*m)。

注意：tot=1。

#include
      
       #include
       
        #include
        
         using namespace std;int n,m,S,T;namespace nwf{    const int maxn=210,maxm=210,inf=0x3f3f3f3f;    int tot=1,first[maxn],d[maxn],q[maxn],cur[maxn];    struct edge{
    int v,f,from;}e[maxm*2];    void insert(int u,int v,int f){        tot++;e[tot].v=v;e[tot].f=f;e[tot].from=first[u];first[u]=tot;        tot++;e[tot].v=u;e[tot].f=0;e[tot].from=first[v];first[v]=tot;    }    bool bfs(){        memset(d,-1,sizeof(d));        d[S]=0;        int head=0,tail=1;q[head]=S;        while(head
        
       
      

 

最小割：割掉原图的一些边使得S无法到达T，求最小的割边边权和。

最大流最小割定理：

1.最小割等价于最大流。

2.最小割在最大流中一定是满流边，是增广路径中容量最小的边。

3.一条增广路径只对应一条最小割。（如果一条增广路中两条满流且都需要割掉，那一定通过反向边分成两条增广路）

论文：

建模技巧：割断S-T通路的最小代价。

1.强制同属：x向y连容量为inf的有向边，表示节点x在S时节点y也必须在S，节点y在T时节点x也必须在T。

那么如果节点x和节点y必须在同一侧，x向y连容量为inf的双向边。

需要时强制不同属，其中一个反过来就是强制同属了。

例题：Path

2.强制同割：割断边x时，边y也必须割断。

利用强制同属的技巧，强制同割无非是x在S时y也必须在S，x'在T时y'也必须在T。

故x一侧向y一侧连容量为inf的有向边，y另一侧向x另一侧连容量为inf的有向边。

含义是割断x后还可以通过y到T，也就强制y必须割。

这种用法不止强制，可以给边加某个容量就可以代表不同割的代价了。（inf就是承受不起不同割的代价）

3.集合选一：集合点权体现为边权，连在一条链上，最小割就是答案。

例题：切糕

4.选择节点集合：每个点向S和T连边，在S割表示选，在T割表示不选。

最大权闭合子图就是一个例子，先默认正权全选，然后割在S说明选，割在T说明不选，这样代价就可以变正。

例题：NOI2006最大获利

5.处理负权边：不能直接所有边加权，否则会破坏大小关系，只能从建图的角度考虑不影响决策的代价（比如所有点等）。

 

 

【费用流】原始对偶算法（连续最短路+多路增广）

“费用流”通常指最小费用最大流算法，最小费用流算法在后面。

原理：基于每条边的费用进行SPFA构造最短路图，然后严格按照最短路图进行dfs多路增广。

spfa：以T为起点，费用为边权，求出最短路图。（记得SLF优化）

dfs：严格遵循最短路图上的边进行多路增广，记录vis避免走回头路（要回溯），过程中叠加总费用ans=e[i].cost*f。（可以加当前弧优化）

注意：tot=1。

#include
      
       #include
       
        #include
        
         using namespace std;int n,k,S,T;namespace nwf2{    const int maxn=5010,maxm=10010,inf=0x3f3f3f3f,N=5005;    int first[maxn],cur[maxn],tot=1,q[maxn],d[maxn],ans=0;//    bool vis[maxn];    struct edge{
    int v,f,c,from;}e[maxm*2];    void insert(int u,int v,int f,int c){        tot++;e[tot].v=v;e[tot].f=f;e[tot].c=c;e[tot].from=first[u];first[u]=tot;        tot++;e[tot].v=u;e[tot].f=0;e[tot].c=-c;e[tot].from=first[v];first[v]=tot;    }    bool spfa(){        memset(d,0x3f,sizeof(d));        d[T]=0;vis[T]=1;        int head=0,tail=1;        q[head]=T;        while(head!=tail){
    //            int x=q[head++];if(head>N)head=0;            for(int i=first[x];i;i=e[i].from)            if(e[i^1].f&&d[x]+e[i^1].c
         
          N)tail=0;}                    vis[e[i].v]=1;                }            }            vis[x]=0;        }        return d[S]
         
        
       
      

 

最小费用流：spfa当且仅当最短路费用对答案有贡献时继续（d[S]<0），否则直接退出。

负圈：费用流中如果一开始就存在负圈，就必须消圈才能求解。

方法是每次后将圈内容量最小边满流（留下反向边）同时费用累加进答案，圈内其它边加上一样的流量（总流量不变但费用变低），然后接着跑spfa直至没有负圈。

消圈算法：另一个费用流算法，涉及到负圈的知识，可以忽略。

原理是消圈定理——流量为f的流是最小费用流当且仅当不存在负费用增广圈。

如果在一个流网络中求出了一个最大流，但对于一条增广路上的某两个点之间有负权路，那么这个流一定不是最小费用最大流，因为我们可以让一部分流从这条最小费用路流过以减少费用，所以根据这个思想，可以先求出一个最大初始流，然后不断地通过负圈分流以减少费用，直到流网络中不存在负圈为止。关键在于负圈内所有边流量同时增加是不会改变总流量的，却会降低总费用。

最常用的连续最短路(单路或多路)每次都贪心地取最小费用路径在增广，所以每次增广的都是最优的，不存在增广过程中产生负圈的可能，但要注意它无法处理图一开始就存在负圈的情况。

拆费用技巧：当题目要求cost(x)=a(x)*flow(x)^2时，将边 x 拆成x条边，cost(i)=2*i-1。这是因为x^2=Σ(2*i-1)。

收集了一个教程：

 

 

【二分图】

一个无向图是二分图的充要条件是不存在奇环。

常用技巧：棋盘图黑白染色形成二分图&&网格x-y形成二分图。

S向左侧xi连边，右侧yi向T连边，边权全部为1。

1.最大匹配=最大流

每一条流量为1的增广路对应一条匹配边，最大流就是最大匹配

2.最小覆盖集=最小割

最小覆盖集是选择最少的点使每条边至少有一个端点被选中，即S-T的所有通路必须割断——最小割

3.最大独立集=总点数-最小覆盖集

最大独立集和最小覆盖集互为补集，因为只要不选最小覆盖集的所有点，每条边就至少有一个点不被选中，即最大独立集。

同理，最大点权独立集=总权值-最小点权覆盖集。

4.最小路径覆盖：在DAG找尽量少的路径，使每个节点恰好在一条路径上(点不相交)。

做法：将每个点x拆成x和x'分别放到二分图两部，如果u到v有一条边，则连边u,v`，然后二分图最大匹配。

初始未匹配ans=n即每个点单独为一条路径，匹配一条说明连了两点，ans-1，所以最终ans=N-最大匹配。

原理是在最小路径覆盖中，每个点都有一个后继节点，没有后继节点的节点就是链结尾，数量就是链数。

值得一提的是中要求最小链覆盖，只要floyd传递闭包处理出可达信息之后，就是最小路径覆盖了。

5.二分图最大权匹配：要求完美匹配就跑最小费用最大流，不要求完美匹配就跑最小费用流。

 

【最大权闭合子图】

参考：

问题：给定带点权DAG，求最大点权和闭合子图。（闭合子图是原图的一个点集V，满足V中节点的后续节点也在V中）。

1.S向所有正权点连边，所有负权点向T连边，0不管，流量均为绝对值。保留原边，流量为正无穷。

2.对于正权点x，割掉与S的连边表示舍弃S，离开闭合子图。对于负权点y，割掉与T的连边表示舍弃T，加入闭合子图。

3.初始所有正权点都属于闭合子图，所有负权点都不属于闭合子图。对于每条S-T增广路代表原图一条起点为正权点终点为负权点的有向链，要么把负权点加入闭合子图，要么把正权点离开闭合子图。

最终，最大权闭合子图=所有正权点之和-最小割。

 

【题目列表】

1. 最大流

2. 最大流

题意：给定n*m的数字表格，数字只有0~4。有k只蜥蜴待在一个格子中，能跳到曼哈顿距离<=d的另一个格子或跳出界，每跳离一个格子该石柱高度-1，为0不能跳。求最少有多少蜥蜴无法跳出界。

题解：每个柱子作为一条容量为柱高的边，S向所有蜥蜴所在柱顶连边，能跳出界的柱底和T连边，跑最大流即可。

3. 最大流

题意：n个站，m艘飞船按各自顺序循环飞行，每艘飞船有给定载客量，求k个人最少需要多少时刻从S到T。m<=13,n<=20,k<=50。

题解：分层图最大流

枚举时刻T（至多100），每次飞行从下一层连向上一层，每个点往上层点连无穷边。建S连向每层的S，建T连向每层的T。

最大流支持加边，所以枚举优于二分。

4. 最小费用最大流(费用流)

题意：给定n*n的非负整数矩形，从(1,1)走到(n,n)并将路上经过的数字加入答案后数字变0，走k次，求最大答案。

题解：每个格子拆成一条容量1费用-num的边，另外每个格子还需要一条容量inf费用0的边（可以重复经过，不可重复取数），然后右下连边，S向(1,1)连容量k的边，(n,n)同理。

最小费用最大流就是答案。（最大流保证走k次）

5. 最小费用最大流(费用流)

6. 最大流+最小费用最大流(费用流)

题意：给定n个点m条容量为ci扩容费用为di的边，第一问最大流，第二问最少扩容费用使得最大流增加K。（每条边花费di扩容1）

题解：残量网络。

在原图上费用为0跑最大流，然后每条边附加一条容量为inf费用为di的边，新增超级源S向1连容量K费用0的边，这样跑最小费用最大流就能得到增加K流量前提下的最小费用。

跑完第一问的最大流后，残量网络的含义是已确定从S到T大小为ans的流之后的剩余图，由于新图同样需要这个流，所以可以直接在残量网络上跑，修改S和T对残量网络没影响。

也可以全部建新图，超级源S向1连容量K+ans的边，答案不变。

7.网络扩容问题（蓝书）：给定带容量有向图，求哪些边满足只改变该边容量能存在流量为C的流。

题解：首先一定是最小割边，枚举判断。优化：直接在跑一次最大流的残量网络上做，跑到C就退出。

8. 二分图最大匹配

题意：n*m的网格图有一些空地，求用1*2矩阵至多不重叠覆盖多少空地。

题解：对网格图按i+j奇偶染色，就可以保证相邻两格异色，然后就是二分图最大匹配了。

9. 最大独立集

10. 最小费用最大流(费用流)

★这道题比较重要，直接看。

思想：拆点表示次数，提前计算未来影响。

11. 最大权闭合子图 或 最小割

题意：给定n个点m条边，点有负点权，边有正边权，要求选择一些点使得点权+边权最大。

题解：将边视为一个点连向两个端点，然后就是在二分图上进行最大权闭合子图，复杂度O(n√n)。

提出另一种解法是最小割，也是S和T都向每个点连边。

根据一条增广路有且仅有一条边割断，连S表示选，连T表示不选，然后把代价放在最小割上。

具体内容参考上面的题解链接。

12. 二分图博弈

题解：二分图染色后转化为哪些点属于某个最大匹配。

找到一个最大匹配后，枚举某个非匹配点出发沿"非匹配边-匹配边”交替走，途中遇到的同侧匹配点都能加入答案。

13. 三分图？

题意：每头牛有可接受的食物列表和饮料列表，一头牛的食物和饮料都满足时视为喂饱，每种食物和饮料只有一份，求最多喂饱几头牛。

题解：S，饮料，牛，牛2，食物，T。

14. 最小覆盖集

题意：给定n*n方格图，k个物体，一次操作可以消除一行或一列的物体，求最少操作次数消除所有物体。

题解：最小覆盖模型的出处，将物体的x-y连边构成二分图，要求选择最小点集满足每条边至少一个端点被选中，即最小覆盖集，转化为最小割。

15. 最小路径覆盖

16. 最大权闭合子图

题解：详见，将依赖关系建成点与点之间的边即可。

17. 最大权闭合子图

题意：转化模型后是图中存在一些保护关系，要吃b必须先吃a，求最大价值。

题解：环和环的内向树无解，这恰好可以通过拓扑排序得到所有有解的点，然后最大权闭合子图。

18.  最小割

题意：给定n*m方格，每个方格可以填1~k的数字，相邻方格数字之差不能超过d。给定v数组，v(i,j,k)表示方格(i,j)填数字k的代价，求最小代价。n,m,k,d<=40。

题解：不考虑相邻限制，每个方格取最小，每个方格建立节点0~k，i向i+1连边容量为v[i+1]，所有底端连向S，所有顶端连向T，这样最小割就是最小代价。

考虑加入限制，第x层的节点向第x-d层的相邻节点连边，这样如果割掉x上面的边，就强制必须割掉相邻方格的[x-d,x+d]的边。

 

 

【网络流24题】

题目链接：

1.「网络流 24 题」搭配飞行员

题解：二分图匹配

2.「网络流 24 题」太空飞行计划

题解：最大权闭合子图

3.「网络流 24 题」最小路径覆盖

题解：最小路径覆盖

4.「网络流 24 题」魔术球

题意：n个柱子，往上顺序放数字，必须满足相邻两个数字和是完全平方数，求至多可以放到多少。

题解：最小路径覆盖

枚举答案ans，满足条件的数字之间连边，转化为最小路径覆盖，枚举到需要n+1条为止，ans-1即为答案。

每次直接在残量网络上新加边即可。

5.「网络流 24 题」圆桌聚餐

题意：n个单位的代表人数ri，m个会议桌的容纳人数ci，来自同一个单位的代表不在同一个餐桌就餐，求是否存在合法方案及方案。

题解：二分图多重匹配。

S向n个点连容量为ri的边，m个点向T连容量为ci的边，n*m相互连容量为1的边，这样同一单位的人必须坐不同的ri桌，如果最大流为Σri则有解，满流边的分配方案是一组可行解。

也可以贪心+线段树维护，每次从大到小填会议桌，只要从大到小枚举人数，每次前k个-1。为了维护单调性，最后若干个相等的数字要减靠后的，这可以通过线段树上二分出该区间来实现。

6.「网络流 24 题」最长递增子序列

题意：给定n个数，1.求不严格最长上升子序列长度k，2.求能同时取出多少个长度为k的不严格最长上升子序列，3.假设能重复取x1和xn，能同时取出多少个……。

题解：用动态规划求出f[i]，一个满足条件的序列的f[]必然严格递增。每个数字拆成 i 和 i+n ，当满足j<i和a[j]<=a[i]和f[j]+1=f[i]时， i+n 向 j 连容量为inf的边。

然后 i 向 i+n连边容量为1的边。S向满足f[i]=1的i连容量为1的边，满足f[i]=k的i向T连容量为1的边，跑最大流即可。

第三问将1和n相关的边改成inf即可（直接在残余网络加边也没问题）。

7.「网络流 24 题」试题库

题意：n道题，每道题有多个所属类别。现在给出m个类别，要求从n道题中抽取m道题组卷，求方案或无解。

题解：二分图多重匹配。

S向题连容量为1的边（每道题用一次），每个类别向T连容量为需求的边，题向其所有类别连边。

8.「网络流 24 题」方格取数

题意：给定n*m的网格图，每格有一个正整数。求取数和最大的方案满足没有取到相邻格。

题解：二分图最大独立集。

互斥求最大的问题直接考虑独立集就可以了，黑白染色后相邻格连边，求二分图最大独立集。

9.「网络流 24 题」餐巾计划

题意：给出n天需要的餐巾数f[i]，每天可以价格P购进餐巾，每天用完的餐巾可以价格F送快洗M天后取，或价格S送慢洗N天后取，或囤积，求最小代价。

题解：问题的焦点在于满足每天的需求的同时，需要等量的流选择快洗或慢洗或囤积。好在每天使用餐巾数量一定f[i]，可以静态建图。

每天拆成二分图的一对点，Xi表示当天过后未洗餐巾，Yi表示当天开始已有餐巾。

1.每天需要f[i]的餐巾，Yi向T连容量为f[i]费用为0的边。（用最大流来保证）

2.每天能购进餐巾，S向Yi连容量为inf费用为P的边。

3.每天剩余f[i]的未洗餐巾，S向Xi连容量为f[i]费用为0的边。

4.每天的餐巾可以送洗或不送洗，Xi向Xi+1连容量为inf费用为0的边，Xi向Yi+N连容量为inf费用为S的边，Xi向Yi+M连容量为inf费用为F的边。

最小费用最大流就是答案。

10.「网络流 24 题」航空路线问题

题意：从左到右n座城市，m条无向边，求满足从1到n再到1且不重复访问的最长路径或无解。

题解：转化为求最长的两条不相交路径。

每个点拆成一条容量为1费用为-1的边，1和n的容量为2，然后最小费用最大流。若最大流不为2则无解。

11.「网络流 24 题」软件补丁

不是网络流，将状态压缩成二进制后求最短路。注意边可以不预处理而是在跑的过程中判断是否有边，以及遇到T是堆顶就退出，这样复杂度比较玄学。

12.「网络流 24 题」星际转移

即

思想：分层图网络流。

网络流判定性问题更适合枚举答案，每次直接在残量网络上加边即可。

13.「网络流 24 题」孤岛营救问题

题意：给定n*m的方格迷宫，边可能为墙或路或门，一共p类门和对应钥匙，钥匙在地图一些格子中，每走一步+1s，求最短时间。n,m,p<=10。

题解：不是网络流。考虑没有门的话，就是直接BFS求最短路。

用P位二进制表示当前获得的钥匙状态，建立2^P层图。每层图表示在当前钥匙状态下的地图，每获得一把钥匙进入新的一层，BFS求最短路即可。

14.「网络流 24 题」汽车加油行驶问题

把油量放进状态，分层图最短路。

15.「网络流 24 题」数字梯形

题意：给定上底为m高度为n的数字梯形，求顶部m个数字开始求m条从顶到底的路径的最大数字总和，依次求满足以下规则之一的答案：

1.点不相交。2.边不相交。3.无限制。

题解：最大权不相交路径问题用流量限制相交，用费用计算权值。1.拆点容量为1，2.不拆点，点连边容量为1，3.容量为inf。

16.「网络流 24 题」运输问题

题解：二分图多重匹配加个费用而已。

17.「网络流 24 题」分配问题

题解：二分图带边权匹配。

18.「网络流 24 题」负载平衡

题意：给定n个仓库的货量ai，求最少搬运量使得全部货量相同。

题解：转化为供求二分图，Xi表示仓库i的供应，Yi表示需求。

设A[i]表示ai-Σai/n，若A[i]>0则S向Xi连容量为A[i]费用为0的边，A[i]<0则Yi向T连容量为-A[i]的边。

然后表示相邻运货连Xi和Xi+1，表示囤积连Xi-Yi。

本来运货应该是n^2种关系，由于可证跨仓库运货等价于相邻仓库运货，所以只有n种关系，这是常见套路。

19. 「网络流 24 题」深海机器人问题

题意：给定网格图，每条边有只能取一次的价值，有若干机器人在一些出发点要到达一些目标点（不限出发和到达点的对应关系），求最大价值。

题解：走路问题。

S向出发点，目标点向T连边。每条边连容量为1费用为价值的边，用来取价值。再连容量为inf费用为0的边，用来通过。

顺便提一下，求无向图最多边不相交路径数，只需要每条边容量为1跑最大流。

20.「网络流 24 题」最长 k 可重区间集

题意：给定n个开区间，要求选择一个区间集合使得 ① 每个点至多被覆盖k次 ② 区间长度之和最长。

题解：本质上是最大权不相交路径，这里允许相交k次。

离散化端点为1~m，S向1连边，m向T连边，i向i+1连边，都是容量为k费用为0。

每个区间左端点向右端点连边容量为1费用为区间长度。最大费用流就是答案。

每次覆盖相当于分出1流量的流到上面的边，这样至多分流k。

21.「网络流 24 题」最长k可重线段集问题

同上。

22.「网络流 24 题」火星探险问题

同“深海机器人问题”。

23.「网络流 24 题」骑士共存问题

二分图最大独立集，见：

 

【有上下界网络流】

参考： by liu_runda

<无源汇上下界可行流>相当于重建图后跑最大流。

如果存在一个可行流,那么一定满足每条边的流量都大于等于流量的下限.因此我们可以令每条边的流量等于流量下限,得到一个初始流,然后建出这个流的残量网络：每条边的流量等于这条边的流量上限与流量下限之差(真正建图)。（不用真的建原反向边）

这个初始流不一定满足流量守恒,因此最终的可行流一定是在这个初始流的基础上增大了一些边的流量使得所有点满足流量守恒.

因此我们考虑在残量网络上求出一个另不满足流量守恒的附加流,使得这个附加流和我们的初始流合并之后满足流量守恒.即:

如果某个点在所有边流量等于下界的初始流中满足流量守恒,那么这个点在附加流中也满足流量守恒,

如果某个点在初始流中的流入量比流出量多x,那么这个点在附加流中的流出量比流入量多x.

如果某个点在初始流中的流入量比流出量少x,那么这个点在附加流中的流出量比流入量少x.

循环流只要求每个点流量守恒，这启发我们建立S、T来引流。（S、T只是引流的作用，如果本来只填下界就流量守恒那甚至不用跑最大流了。）

入度>出度时(in[x]>0)时，需要流出去，所以从源向点引一条容量in[x]的边，引诱它流出去。

因为源进来的流量不是真的流量，而出去的流量却是真的，如果平衡了，流出去的就相当于补足原来多的入度。

入度<出度时(in[x]<0)时，需要流进来，所以从点向汇引一条边，引诱它流进来。同上。

为何这样正确？源和汇的作用只是引诱，让入度多的点流向出度多的点，最终实现流量平衡。

由于源汇连出来容量相同(一入度对应一出度，多余量也一定相同)，所以如果最终满流就实现了流量平衡，此时源汇就可以无视了。

所以如果最大流==S邻边流量上界之和说明存在可行流，流量为下界流量和(初始流)+最大流(附加流)

1.加边时记录每个点入度和出度(in[i])。

2.根据in[i]建源汇连新边。

最大流

3.检验源点出去的边是否满流。

<有源汇上下界可行流> 

要求一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制。

S流不进，T流不出，S的流出量又和和T的流入量相等，这启发我们从t向s连一条容量inf的边，然后跟上面一样处理(建SS,TT)即可。

判断可行方法与上相同(判断最大流与S邻边)，最终t-->s的反向边上存着可行流的总流量(不需要再加原来的下界流量)。

为什么不需要再加原来的下界流量？因为最初根据下界设置基准流量时，基准流量汇集为终点T的in[T]中(入度有余)。

而超级源SS正是把in[T]通过t-->s引向出度有余起点S，所以t-->s的反向边上存着基准流量。

在后来为了流量平衡的增广中，影响到总流量的增广一定会影响到T-->S这条边（很多边的增广只是互补，没有影响t-->s边就不会影响总流量）

从另一方面解释：总流量==S的总流出量==T的总流入量==T-S边的流量。

<有源汇上下界最大流>先和上面一样从t向s连边，然后跑可行流(建SS,TT)，判断可行。

再以s、t在残量网络上跑最大流，该最大流就是最终答案！(不用做什么额外处理，因为额外边全部满流了)

要注意的是原循环流流量存在终点往起点的反向弧中了，最后跑最大流时自然会计算进去。

答案就是最后一次最大流。

会不会增广的时候使得一些边不满足流量下限?

不会。因为我们一开始建的就是把流量下限拿出去之后的图，而之后的操作(如最大流)都是符合流量平衡的，极端情况下就都等于流量下界而已(下界符合平衡时)。

<有源汇上下界最小流>先跑有源汇可行流，然后反向跑t-->s的最大流(增加反向边流量相当去减去正向边流量)，答案是可行流-最大流。

<上下界最小费用最大流>先找原图的负圈消去，然后跑可行流(不会产生负圈)，最后跑s-t/t-s最小费用最大流/最小费用流。

最小费用循环流：找图中的负费用增广圈增广，对于必须满流的边可以设cost为负无穷。

因为循环流没有最大流，若要在循环流中寻找极限值可以尝试附加费用。

 

1927: [Sdoi2010]星际竞速 最小权路径覆盖

bzoj 3876 支线剧情

2055: 80人环游世界

最小割 k覆盖 密度子图 上下界

费用-优先级 循环 流X费√

bzoj 3550 线性规划与网络流

【稳定婚姻问题】

每个尚未订婚的男士在他没有求过婚的女士中选一个最喜欢的求婚，然后女士选择向她求婚的最喜欢的一个(包括原未婚夫)订婚。

开始将所有男士入队，然后每次匹配后失配的男士再次从尾端进入队列。

男士优先选择喜欢的结果就是男士最优、女士最差的搭配，反之。

 

  有上下界网络流(最大流)