费用流题解
说在前面
网络流学的真的是很爽啊，每次一道题都要敲上百行，各种模板套上去就好，费用流虽然还不是太熟练，但是也写了几道题练手。
费用流：费用流和最大流相比，就是多了费用这一点，而这种求法主要是利用SPFA进行求最短路和增广路，如果求出出来增广路，那么这不但是一个最大流，还是费用最小（最大）的费用流。
最大流问题要求从源点S流出尽可能多的流量，流过一条或多条边，到达汇点T，且每条边上流过的流量不大于该边的流量限制，一个单位的流在某条边上产生的费用等于边的费用。而最小费用最大流问题就是要求在流量达到最大的情况下，总费用最小。
由最大流的相关知识可知，当且仅当不存在S到T的增广路时，图中的流达到最大。那么我们可以每次从S流出一个单位的流量到达T，使得这个单位流量所产生的费用最小。
从“形”的角度观察这个问题，每个单位的流在当前网络中产生的最小费用，等价于当前网络中S到T的最小权值路径的权值，即S到T最短路的长度。因此，可以用SPFA求最短路，每次选择残留网络中最短的增广路进行增广，直到不存在增广路为止，可以证明找到的最大流的费用一定最小。分析这个算法的时间复杂度，如果增广次数是w，每次 ...
最大权闭合子图
最大权闭合子图最大权闭合子图其实就是通过一系列的证明，可以求证出来，用边权为正的累加和减去图的最大流就是这个图的最大权闭合子图。证明过程两天前写过一遍，但是丢掉了，实在不想去写了。
并且最大权闭合子图的题目拥有难度的并不多，也就下面这道题有一些难度，证明过程直接粘贴讲稿的QAQ
证明过程
了解了最大权闭合图的概念，接下来我们就需要知道如何求最大权闭合图。首先我们将其转化为一个网络(现在不要问为什么,接下来会证明用网络可以求解)。构造一个源点S，汇点T。我们将S与所有权值为正的点连一条容量为其权值的边，将所有权值为负的点与T连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。
首先引入结论，最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图，接下来我们来说明一些结论。?证明:最小割为简单割。
引入一下简单割的概念：割集的每条边都与S或T关联。(请下面阅读时一定分清最小割与简单割，容易混淆)那么为什么最小割是简单割呢？因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。
证明网络中的简单割与原图中闭合图存在一一对应的关系。(即所有 ...
网络流-最小割
说在前面
首先是最小割，这个最小割真的是非常Exciting啊，好像讲稿里面什么都没有些QAQ，真的是超级难受。然后自己百度了好久在弄明白了最小割的定义和求法（垃圾讲稿毁我青春！:angry:）
最小割最小割定义：
割：设Ci为网络N中一些弧的集合，若从N中删去Ci中的所有弧能使得从源点Vs到汇点Vt的路集为空集时，称Ci为Vs和Vt间的一个割。通俗理解，一个图或网络的割，表示一个切面或切线，将图或网络分为分别包含源点和漏点的两个子集，该切线或切面与网络相交的楞或边的集合，称为图像的割。最小割：最小割，图中所有的割中，边权值和最小的割为最小割
上面都是从百度百科里面粘过来的，用通俗易懂的话来说，假如你们家有一个复杂的水管路，然而你惹了 JZYZ 的 Centry 大佬，这位 Centry 大佬决定让你家没有水喝，一滴水都没有的那种，于是派Xorex 来执行任务。
Xorex 为了解决这个问题，只能用键盘砸断水管，这个砸断水管使得边不连通的过程就是割。但是有些水管粗有些细，粗的需要砸的时间长，细的则短一些，Xorex 也知道砸水管很耗费时间，那么这个设计最短时间断掉你家水源的方案就 ...
最大流的建图
写在前面
写完了几道网络流最大流的问题，Dinic算法也练习的差不多了，然后来总结一下网络流的建图问题，毕竟图论的难点不在于算法实现，毕竟有模板可以背，而是在于建图能力，这方面需要提高的。
P1324 晚餐题目描述：
农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N (1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料.
输入：
第一行: 三个数: N, F, 和 D第2..N+1行: 每一行由两个数开始F_i 和 D_i, 分别是第i 头牛可以吃的食品数和可以喝的饮料数.下F_i个整数是第i头牛可以吃的食品号,再下面的D_i个整数是第i头牛可以喝的饮料号码.
输出：
第一行: 一个整数,最多可以喂 ...
网络流-最大流求解
说在前面
其实很早以前就知道有这个网络流算法了，而且据说是特别难的（毕竟当时我连DP和图论都在仰望中）现在接触到了，很神奇，但是并没有想象中的那么难 （毕竟可以背模板）
这一篇主要是我最网络流的最大流的理解以及在求最大流的时候的Ford-Fulkerson算和Dinic算法。
网络流网络流概念：
什么是网络？网络其实就是有向带权图。为什么要叫网络，是因为权值是容量，容量意味着可以在单位时间内经过的上限，但是可以比上限小。比如说我们一个运输的管道，每段管道都有一个最大水量，如果超出了这个最大水量，就会爆开水管，而这个运输管道系统就是一个网络流。
最大流：
寻找网络G上可能的最大流量(和一个有最大流量的可行流方案)，即为网络G上的最大流问题。
增广路径增广路径(可改进路径)的定义：
若P是网络中连结源点s和汇点t的一条路，我们定义路的方向是从s到t，则路上的弧有两种：
前向弧—弧的方向与路的方向一致。前向弧的全体记为P+；
后向弧—弧的方向与路的方向相反。后向弧的全体记为P-；
设F是一个可行流，P 是从s到t的一条路，若P满足下列条件：
在P+的所有前向弧(u,v)上， ...
二分图匹配题解
说在前面：
终于搞完了二分图匹配，所以特意来总结一下QAQ
NOI2009 变换序列题目描述：
输入：
第一行包含一个整数N，表示序列的长度。接下来的一行包含N个整数Di，其中Di表示i和Ti之间的距离。
输出：
如果至少存在一个满足要求的变换序列T，则输出文件中包含一行N个整数，表示你计算得到的字典序最小的T；否则输出”No Answer”（不含引号）。
题解：这道题首先你学要知道这个公式的意思是什么，上面这个指的是给你一个队列，这个队列是1到n的所有元素，并且代表着是你要求的一个队列和1到n这个顺序队列通过一个公式求出来的距离，公式：
1d[i]=min(a[i]-b[i],n-|a[i]-b[i]|)
大概就是这样。
所以说我们可以通过上面的那个公式建立起来一个联系，也就是说，给定你的队列d是一个通过两种方法求出来的，分别是 a[i]-b[i] 和 n-|a[i]-b[i]| ，我们需要判断他是由哪一个过来的，可能是其中一个，也有可能是其中的两个，这样我们将给定的队列和1-n进行连接，形成一个二分图。
建立起来二分图之后，我们就可以开始求要求的那个序列了也就是说，对 ...
二分图匹配
二分图
简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 U 和V ，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。
二分图的匹配最大匹配：
一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
完美匹配：
如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配.显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。
交替路：
从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：
从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。
匈牙利算法
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核 ...
LIST 要学会的东西
写在前面
靠着疯狂水第十页的大水题，然后成功挤进OJ排行榜的第一页，但是怕是马上杨树神就超过我了，不过一个月内再次进入应该还是没问题的，但是需要勤学知识点，勤敲代码啊。不想 NOIP2017 一结束就滚回去学文化课就需要努力的……
所以说列出来了一些要学会的东西，能力才是最重要的，刷题量只是虚的，只能拿出来看看而已……加油吧！
LIST1.二分图匹配；
2.Hash表；
3.分块；
4.搜索；
写在后面上面都是一些很虚的东西，OJ里面的例题并没有什么多少，重要的是这种能力，所以才会扒出来重点学，尤其是搜索，自己的搜索能力必须尽快提高，DFS要写的出神入化才行，分块要用线段树的例题写一写，然后Hash跟着刘神学，二分图跟着晗神学QAQ，东西不多，但是需要真的掌握！
查分约束系统
查分约束：
差分约束系统其实就是一种限制的关系，转换为一张图，然后跑一边SPFA，更新一遍，
P1984奖学金题目描述：
期末考试终于完了，老班决定召开班委会，内容嘛，则是可爱的奖学金的问题，她叫来了一些班委，每位班委提出了自己的意见：“我认为同学a的奖学金应该比b多！”老班决定要找出一种奖学金方案，满足各位班委的意见，且同时使得总奖学金数最少。每位同学奖学金最少为100元且都为整数。
输入：
第一行两个整数n,m，表示同学总数和班委意见数;
以下m行，每行2个整数a,b，表示某个班委认为第a号同学奖学金应该比第b号同学高
输出：
若无法找到合法方案，则输出“impossible”(不含引号）；否则输出一个数表示最少总奖学金。
题解：我们将里面的a>b转换为a=b+1，就可以建造一张这样的关系图了b到a存在着边权为1的路，然后我们就跑一遍SPFA美滋滋，更新出来所有符合要求的奖学金，如果不符合要求就直接退出输出impossible，如果符合就累加起来输出。
代码：1234567891011121314151617181920212223242526272829303132 ...
快速输入和输出
写在前面
今天晚上闲来无事，就将各种类型的快读和快出写了出来（不会写浮点型）；
读入int比如int是节省时间最快的，超级快！！！
123456789101112131415inline int In_int(){ int This=0,F=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') F=-F; ch=getchar(); } while(ch>='0'&&ch<='9') { This=(This<<1)+(This<<3)+ch-'0'; ch=getchar(); } return This;}
读入char其次就是char类型，节省时间一般般。
123456in ...