第一题
求二分图匹配，输出谁和谁匹配
使用反向边是否存在流量来输出路径。
第二题
求有向图的最大权闭合子图
将正权点连接s,容量为点权,负权点连接t容量为点权绝对值,所求得的一个割将图分为两部分,我们发现所有正点权的和减去该简单割，便是与s相连的闭合图的权，因为最小割所以最大权闭合图（即给定常数c，求c-a的最大值，等价于求c减去a的最小值）。注意跑完最大流以后，与s相连的点构成的点集就是最大权闭合图。学会了使用bfs之后 的lv数组来输出路径
第三题
求DAG的最小路径覆盖
用原图建立一个两层的新图，如果原图中存在边i->j我 们建立的新图就有第一层的点i流到第二层的点j，最后建立超级源点流向 所有的第一层图的点，建立超级汇点，由所有第二层的图流入，用DAG的总点数减去去所求的最大流就是最小路径。
在构造的二分图中的最大流映射回原图，发现每个点最多有一个入度，一个出度，显然整个图形成了一些不相交的链，于是点数减去边数就是联通块的个数。即总点数减去匹配数就是最小路径数。
第四题
依旧是是一个最小路径覆盖的问题，我们考虑把球当作点，把盒子当成路径，那么很明显，连边方式就是i->j当且仅当i<=n且j<=n且i+j=k^2.
但是这样子做我们只能解决这样一个问题: 给你从1到n的n个球我们可以找到最少的盒子来装球。
仔细分析发现题目给的问题可以二分处理，我们二分来判断n个盒子能不能装到k个球就可以了。
第五题
给m组人，每个人要分到不同的桌子上，每个桌子可以一定量的人，组内的人不能坐在一个桌子上， 网络流问题，s连到组，流量组内人数，桌子连到t，流量为可以坐下的人数，组与桌子自由组合， 流量为1。
第六题
让你求一个数列的最长不下降子序列的长度k
然后求这个序列最多可以分出多少个长度为k的子序列，
再求如果可以多次使用第一个元素和最后一个元素，可以分出多少个长度为k的子序列
我们考虑到每个元素dp的值（dp[i]表示以i结尾的最长不下降子序列的长度），并以dp值为标准，给所有点分层，并给所有第一层的点连s，所有最后一层的点连t， 如果i<j且a[i]<=a[j]我们就连一条边i->j，如此如果每当从s流到t,就是一个子串,考虑到一个点只能用一次,拆点限流就可以了。
第七题
给你一个试题库，告诉你每个题目的类型（一个题目可能属于多种类型），让你 用这些题为每个类型组一套题（告诉了你每套题包含的题数），每道题只能用一次，
类型在左，题目在右，s连类型，流量为该套题的题数，类型连题目流量1，题目连 t流量1，如果最大流不够要求的题目数量，说明无法组成套题。
第八题
什么怪东西，明明是深搜题
第九题
有一个 m 行 n 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。
对于格子我们令k=行数加列数，
对于所有的k&1==1内部，无边，
对于所有的k&1==0内部，无边。
于是取走元素就成了：
拿走点，使得这些点覆盖所有边，于是剩下的点就是独立的了， 没有边互相连。就是我们要的答案，所以就成了 最小点覆盖二分图
第十题
此处不方便证明，详情见： 建图与证明
第十一题
给你一个城市数组，这些城市从左往右分别对应从东到西， 要求你从最西边的城市出发，到达最东边的城市，在从最东边的城市出发，到达最西边的城市 除了最西边和最东边的城市以外，其他城市只能经过一次 让你求最多经过多少城市，
考虑最大流，s连最西边的城市，最东边的的城市连t，容量2，对于他给的边只连从东到西的边， 对于一个城市只经过一次考虑拆点限流即可。
- 本文作者： fightinggg
- 本文链接： http://fightinggg.github.io/yilia/yilia/PGYGU3.html
- 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！