网络流
是指在一个每条边都有容量（capacity）的有向图分配流，使一条边的流量不会超过它的容量。
最大流
Dinic
Dinic算法（又称Dinitz算法）是一个在网络流中计算最大流的强多项式复杂度的算法，设想由以色列（前苏联）的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。
最大流例题
[Usaco 2007 Open] Dining吃饭
题意： 有N头牛，F种食物和D种饮料，每头牛有多种喜欢的食物和饮料，每头牛只可以吃一种食物和饮料，且每种食物和饮料都只能被一头牛吃掉。一头牛满意当且仅当它吃到满意的食物并且喝到想喝的饮料，问最多可能让多少头牛满意。
最小割
最大权闭合子图
现在有一个有向图，每个点有点权，点权可正可负。对于任意一条有向边i和j，选择了点i就必须选择点j，你需要选择一些点使得得到权值最大。
解题
将由源点S向权值为正的点连流量为i的边，将权值为负的点向汇点连边
限制关系连流量为INF的图
[NOI2006 最大获利]
建权值为Ci的一个图像Ai与Bi建图 转化为最大权闭合子图
其他
二分图最大点权匹配
二分图最大点权独立集
费用流
- 最大费用流
- 最小费用最大流
连续最短路算法
- 贪心思想
- 从源点开始每次寻找总费用最小的增广路
- 直到不能增广为止
[SDOI2009]晨跑
Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校，保证寝室编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以 在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。Elaxia耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天 数尽量长。 除了练空手道，Elaxia其他时间都花在了学习和找MM上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
[SDOI2007]修车
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
将每个人拆成n个点
第i个点代表这个人修的车中倒数第i辆
将每辆车向这些点连边，流量为1
的费用为f[i][j]*i
源点连向车，工作人员向汇点连边
[SDOI2016]数字匹配
有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。 若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数， 那么这两个数字可以配对，并获得 ci×cj 的价值。 一个数字只能参与一次配对，可以不参与配对。 在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
以奇数和偶数因子建二分图
[SDOI2013]费用流
Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。
最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。
一个合法的网络流方案必须满足：
(1)每条边的实际流量都不超过其最大流量且非负；
(2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的净流入流量，这个值也即该网络流方案的总运输量。最大流问题就是对于给定的运输网络，求总运输量最大的网络流方案。
上图表示了一个最大流问题。
对于每条边，右边的数代表该边的最大流量，左边的数代表在最优解中，该边的实际流量。需要注意到，一个最大流问题的解可能不是唯一的。 对于一张给定的运输网络，Alice先确定一个最大流，如果有多种解，Alice可以任选一种；之后Bob在每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于P。总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到，Bob在分配单位花费之前，已经知道Alice所给出的最大流方案。现茌Alice希望总费用尽量小，而Bob希望总费用尽量大。我们想知道，如果两个人都执行最优策略，最大流的值和总费用分别为多少。
[codevs 1227]方格取数2
给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大
[BZOJ 3438]小M的作物
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子 有1个（就是可以种一棵作物）（用1…n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植 可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益 ，小M找到了规则中共有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以 获得c2i的额外收益，所以，小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？
[BZOJ1283] 序列
给出一个长度为 的正整数序列Ci，求一个子序列，使得原序列中任意长度为M的子串中被选出的元素不超过K(K,M<=100) 个，并且选出的元素之和最大。