艾尔法的网络流

· · 个人记录

为了避免以后麻烦，[x,y,f(/f'),(w)]表示从x到y流量为f（或下界为f上界为f'）（如果有费用的话）费用为w的边

HDU2485

英文翻译大赛I

n$个点$m$条边的有向图，问至少删去多少个点，可以使所有从$1$到$n$的路径的长度都大于$k

这道题出出来倒不是因为他建模有多么诡异，思路有多么难想，而是要和大家区分一下一些事情。

这里我们思考这样一个建模，对于每一个点拆点，连[i,i+n,1]。这种建模可以很快的表示出从1到n的所有路径，这种表示方法可以让每个从1到n的路径都至少有一个点被割掉了。（如果流量为inf的话就是至少有一个边被割掉了）

那么对于这道题，我们先做一遍Floyed（好像两遍SPFA也行），然后设d[i,j]表示最短距离，由于边的长度是固定的，所以，我们可以发现，不符合一个条件的路径一定有一条边(u,v)，满足dis[1,u]+len(u,v)+dis[v,n]\leq k，也就是 dis[1,u]+dis[v,n]<k

然后我们对于这样一组(u,v)，连[u+n,v,1] ，然后做最小割，乍一看，好像是所有小于k的路径都被割掉了，不过大家考虑一个问题：两条路径交在一起之后，未必是两条路径。
比如我们画个图。

你看这个图假设(abc)(ade)都是小于k的路径，但是a和图中虚线构成的是大于k的路径，假设你通过某种操作，导致整个虚线都在小于k的路径里面。（被好几个类似于这样的结构一段一段插了进去）
如果我们把这个图插入刚刚的建模中，就会发现，虽然中间的那个路径大于k，但是我们一样把它放到了建模里面，也就意味着这个路径上一定有一个点会被割掉，而事实上，我们如果要干掉所有小于等于k的路径，未必要割掉这条路径上的点，因此这个建模就错误了。

正确的建模其实非常简单但也非常的巧妙。
我们首先把们给点拆点，因为除了起点终点不能删，其他点可以被删且最多被删除一次，所以我们可以可以拆点后限制流量为一，然后把原图搬上去。形式化的，对于一个点u\neq1,n，建立[u,u+n,1]，对于一条边(u,v)，建立[u+n,v,inf]
此时，考虑利用费用流的模型，把边修改为[u+n,v,inf,1]，这样每次SPFA的时候，如果当前流的费用\leq k，意味着还要割，就接着流，否则就停下，这样的话，剩下的残量网络的边构成的图的所有路径的费用都>k

HDU3605

小水题？
英文翻译大赛II

有N(N<100,000)个人要去M(M<10)个星球，每个人只可以去一些星球，一个星球最多容纳K_i个人。请问是否所有人都可以选择自己的星球。

有人管这个trick叫二分图多重匹配，但实际上我觉得多重匹配这个名字过于玄学了。
对于一般的建模，我们直接二分图匹配正常建模即可。不过点数太多了过不去（为了避免有人想卡常我们n直接开到1e6也不要紧）
这个题的m\leq 10是个非常重要的条件，因为我们每个人的选择是有限个，也就是只有2^{m}个。在这种情况下，我们不妨把选择一样的人缩成一个点，再跑二分图匹配就行了。

由于流量不是1了，所以dinic并不比匈牙利快很多。

HDU3338

英文翻译大赛III
由于有图，所以这个题不给题意解释了。

不是个难题也不是个简单题，主要是想推介一下，如何用诡异的方法解决比较特殊的上下界问题。
这个题一看就知道是按照行和列来建图。
所有黑点不管。所有白点单独弄一个点，设这类节点为B，设标有行和的点记为(A,v_A)，设记有列和的点记为(C,v_C)，那么建出边来，有

[S,A,v_A],[A,B,8],[B,C,8],[C,T,v_C]

乍一看，特别不合理，你填的不是1~9的数嘛。不过这张图，我们流量的界是[1,9]，那么我们先全图流1，流量的界就变成了[0,8]，然后就直接做了，这个trick还是值得记录一下。

不过这个题的难点在于……处理输入和输出方案。
输入就是模拟。输出其实就是找一找每一行连向每个点的那个边的流量，建议可以记一下是哪些边，然后就简简单单2333.

HDU4183

英文翻译大赛IV
给你一些点，每个点有一定的半径和频率。两圆相交你才能从一个通向另一个。你有一个诡异的交通工具，和起点、终点。你从起点走到终点只能频率递增，你从终点走向起点只能评率递减。每个点只能用一次。问是否能从起点到终点，然后返回。

限时训练好题：5秒钟必须建好的经典模型。
其实这个题是经典的“限制性不交多路径问题”。这种题可以用网络流很快速地解决，直接从小到大连边，跑网络流，找两条不相交路径，所以要拆点限制流量，问流量是否\geq 2

HDU3081

英文翻译大赛V

$n\leq100

怎么说呢……这个题在大家看来可能很简单，但是确实是我很陌生的一个建模，所以我把它写了出来，方便自己复习使用。

一看这个次数就知道直接做是没法做的，因此我们首先二分一个挑选次数k
我们先建立S,T，然后考虑他们怎么连。
将男孩与女孩之间的流量设为[x,y,1]，然后将女孩与源点之间的流量设为二分的值k，男孩与终点的流量设成k，如果最终流量为n\times k，那么证明可以实现k次。

这个确实我做的时候没想到，后来想想也是，每多流一种方案，不就是可以对于每一个女孩的地方加一个流量，然后均匀的在残量网络中增广后从每一个男孩的点那里流出来嘛（怎么感觉怪怪的……）

这个题最最重点的地方是一个实现的大细节。
我写的时候就被这里坑到了，一定要注意一下。

这个女孩向男孩连边啊，不是简简单单连边，比如有可能两个互为朋友的女孩子，都被一个男生给箭头了（不是），这个时候要用并查集收束一下，避免一个女生两次向一个男生连边。两次向一个男生连边就等同于可能两次选同一个男生了，自然是暴毙的2333.

HDU-3461

嘤语翻译大赛VI
有向图边不重复最短路计数。

【不讲，丢人】

这个大概也是我学艺不精吧……这个建模也不太熟悉，两分钟才明白过味来。

最短路预处理，直接把符合条件的边扔到图里面，然后直接最大流即可。

既然讲了这个题，我们就把类似思路的一个小题放了吧。
数列互不相交LIS计数。
这个就是首先你n^2迪屁一下最长上升子序列，然后把f_i=f_j+1的建立[j,i,1]，然后最大流即可。

美食节

网络流与最优化

【别处讲过：此题时间不够可以不讲】

这种题我们通常称之为时间戳类的网络流。
这类网络流的开山鼻祖大概是修车那个题，由于和这个题几乎一样我们就不单独拿出来说了。

为啥说是时间戳类的呢？如果第j个厨师先后做了a_1,a_2...a_w种菜，那么等待的时间之和为

wt_{1,j}+(w-1)t_{2,j}+...+t_{w,j}

我们发现，等待时间与做菜数量有直接关系，所以考虑分层来完成这个过程。
我们让第j个厨师的第w层，表示这个厨师做了倒数第w道菜，我们把这个关系表示为(j,w)，这样一来，原本的一个厨师，就变成了好几层每层一个厨师，虽然看起来很诡异，但是有很好的效果。
根据网络流的经验，点(j,w)向一道菜品连边，则意味着这一层要做这个菜品，毋庸置疑。

在建立源汇之后，我们网络流的建图为：

比较令人眼前一亮的就是$[plate,(j,w),1,t_{i,j}\times w]

这个连法看起来非常符合我们刚才的设计，但是他为什么跑完最小费用最大流之后就对了呢？
因为由于最小费用的最短路的贪心作用，我们选择的点一定是连续的，也就是选完(j,i)之后我不会脑子有坑去选个(j,i+1000)这种，显然不优秀。
因此我们可以认为，他对于每一道菜，都是贪心的放在合适的位置上，所以构造的方案是合法的（
这样的话，点数为(mp+n)，边数为(nmp)，到此为止，就可以得到大概六十来分的成绩了。

请问！这个网络流为什么慢得要死。不难发现，虽然我们把所有的(j,w)都建了出来，但对于一些w比较大的点，他是不会被用到的，然鹅我们每次还闲着没事去最短路增广他。
由贪心（？）可知，这道题一定是从第一层开始的若干个连续层，所以考虑动态加点。
如果我们曾经加入了(j,top_j)，并且这个点被流过了，则我们加入(j,top_j+1)
那么如何判断是否流过呢？

最简单的办法是写KM，并且既然是写费用流，那么dinic也不会比KM快多少，因此直接KM暴力就行了。
点数降到了n+m+p，非常优秀，直接过。

如果强行用dinic写，好像也是可以判断是否流过的，直接判断他连向汇点的边是否满流就行。（这一句是我口胡的，如果不对直接忽略即可。）

HDU3472

smallwater
有n个单词，有的可以前后颠倒，看是否可以将n个单词首尾相连

相当于混合图判断欧拉路，把每一个字母当成点，然后单词当成边即可。

其实这个题也可以转化成哈密顿路，但是我好像没看见这么转化的，大家可以自己想一想。哈密顿路就是把单词当成点咯。

混合欧拉算是个小套路吧，对笔者来说有点难想

首先，一看到欧拉路的题，就现在自己的演草纸上写下一句话：不判连通性的路径求解都是耍流氓。第一步，先判原图连通性。
然后我们现在来回忆一下基础知识：
无向图中存在欧拉回路的条件？
有向图中存在欧拉回路的条件？
无向图中存在欧拉路的条件？
有向图中存在欧拉路的条件？

以上有四个题儿的答案是：
每个点的度数都为偶数
每个点的入度=出度
奇度数点的个数为0或2
满足第二个条件，若不满足，则只有两个点不满足，且这两个点其中一个点in-out=1，另一点out-in=1

由于本题并不需要输出欧拉路，所以我们这里不圈套圈算法了，我们这里直接看混合图的欧拉路。
混合图之所以难，就是因为无向图和有向图的判断条件并不一样，所以考虑无向图转有向图。
欧拉路之所以难，是因为欧拉回路判断条件唯一，但是欧拉路的判断条件有两种，第二种和确定的点有关，难以维护。所以先考虑欧拉回路怎么做，再考虑怎么欧拉路转欧拉回路。（真nm绕）

我们任意（当然欧皇可以考虑随机，这样就可以直接得到答案了）地钦定每一条无向边的方向。
欧拉回路要求每个点in=out，因此总度数为偶数，存在奇数度数点（(in-out)\%2=1），则直接判掉，不存在解。
那么现在的图，是一张可以进行调整的有向图，并且每个点的出度入度差均为偶数，为了让以后更麻烦，我们定义这个偶数的绝对值是2x 。考虑怎样调整才能让出入平衡。

一看出入平衡，我上来就是一个网络。
首先，有向边没有用，没办法调整，直接弃之不用。无向边，你钦定成了什么样子，就在网络中如何表现出来，然后建立源汇。
对于入度大于出度的点u，我们引导多余流量，构建[u,T,x]，反之补充流量，建立[S,v,x]。设这个网络为G'

求出这个网络的最大流，如果S引出的所有边均满流，则证明有欧拉回路。
在残量网络上查看，所有流量为1的原图边意味着改变了流向，否则意味着没有改变。然后得到了一个有向欧拉图，正常可以输出方案。

那么正确性该怎么证明呢？
考虑我们的一条增广路径S-i-...-j-T，如果我们把i,j之间的路径在G'中全部反向，则相当于i的in++,out--，而j则相当于in--,out++，路径上的其他点没有影响。
而i和S相连，刚刚的建模中，与S相连是出度大于入度，由于入度增加，出度减少，就相当于2x_i-=2，同理相当于-2x_j+=2（负的是因为x是个绝对值嘛），由于我们建图时用的是绝对值嘛，所以就都相当于对应的x减一，也就相当于流了一的流量。

因此，流流量就相当于更改路径方向，调整端点度数。
那么欧拉回路就到此为止了。

对于欧拉路径，容易想到的是在原图中添加一条边[i,j]，然后跑n^2次最大流，行了，这一波就叫做TLE
不过其实，大家不要被这个条件迷惑住了。
刚刚我们是如果有度数差是奇数直接弹出，这里是允许找到两个度数差为奇数的点。
如果懒得思考，那么就正着连一遍，反着连一遍，都调成偶数，看看有没有欧拉路。
不过其实呢，这里也有个结论（不会证但是是对的），如果两个点都是入度大或者都是出度大，则一定无解，否则只需要把入度大的往出度大的点连边，然后check就行了。

费用流

虚假的费用流

这是一道题目是费用流但看起来很像博弈问题的二分最大流问题。
由于Bob事先知道了Alice的选择，所以这并不是一个博弈问题，因为策略是确定的。
可以发现，bob把全部花费都放在流量最大的边上是最优的，所以考虑二分：
问，在最大边流量不超过x的情况下，是否存在最大流。
显然最大流是固定的，但是方案有很多种。并且最坑人的是，本题存在实数。
因此我们写dinic的时候就需要注意把整数变成实数来写，判断的时候用fabs来判断，避免精度误差。

大概就这些了，可能需要特别注意一下这个压缩满流边的思想。

图的难题

P5295

本题做题思路：脑补结论，证明结论，完成建模，流完拉倒（

结论是这样的，一个图符合条件当且仅当E\leq2V-2才有可能满足条件。
这个证明，是当E=2V-2的时候，所有的边有可能构成两棵生成树，当构成两棵生成树的时候，任意添加一条边，都会变成基环树。

然后还不难发现，对于任何一个满足条件的图，他的任何一个子图都满足这个条件，而任意一个子图满足该条件的图一定是符合条件的图（充要），因此我们需要判断任意一个子图满足这个条件。
那么我们思考如何判断E-2V\leq -2呢？
最大权闭合子图

为了避免以后到处翻笔记，这里把这个小基础记录一下。
对于这个子图，它任意一个点的后继都在这个子图中。

求最大权闭合子图的建模中，我们把所有点权为正的点与S相连，边权为点权，点权为负的点与Y相连，边权为点权的绝对值，原图中的有向边不变，边权为极大值。
此时原图的最小割表达了付出代价或舍弃收益的性质。
因此，最终的答案是ans-flow

那么对于这道题，我们需要把边转化成点。
显然这个点的点权应该为1。显然选了边就应该选点，那么也就转化成了最大权闭合子图模型。而原图中的点点权应为-2
那么我们的网络形如[S,E,1],[E,V,inf],[V,T,2]，然后求一波最小割即可得出答案。

HDU4607

【前置知识：混合图欧拉环】
英语翻译大赛VII

题目太长懒得翻译了，unidirectional是“单向的”

对于每条边，我们要么保留，要么删除。 我们先假设两周都能满足条件，那么我们肯定选择花费小的那个来执行，首先不加入任何边，在选择加入或不加入边的时候，对于每个顶点记录入度和出度。
对于每条边，如果a\leq b，则in[v]++,out[u]++,sum+=a，然后连边[v,u,1,b-a]，反之sum+=b，连边[u,v,1,a-b]。

加入一条虚拟的[t,s,1,0]，然后in[s]++,out[t]++转化成了不存在起点和终点的问题。

这个题我们借鉴欧拉环那个题的思路。
那个题是流量为1表示变向，而这个题我们要求建模可以保证流量为1时可以翻转删除和加入。

建立S,T，如果点入度大于出度，则连[S,u,in-out,0]，如果出度大于入度[v,T,out-in,0]
这个和欧拉环那个是反过来的，不过适应性都是一个道理。

把源网络建出来之后，这类入读出度问题，都是考虑源网络上的一条流，能被解释成什么。
我们发现，原图中的一个(u,v)跑过之后，相当于让in[v]++,out[u]++，也就是让起点的出度增加了，这时候不难发现，当我们需要以out增加的形式来平衡一个点的时候，这个点需要连起点，所以入度比较大的应该连起点。

而欧拉环则是跑一条流相当于起点的in增加了，起点应该连通过in增加而平衡的点，所以考虑出度大于入度的，应该反过来连。

HDU3974

英语翻译大赛VIII
志愿者招募
有一道题是NOI2008志愿者招募，我们在看这个题之前先来欣赏一下志愿者招募。

这个题一看就非常动规，但是志愿者种类太多了，并且状态转移无冗余，无法优化，所以思考一下其他的方法。
并且本题有一个独特的限制：每一个人，并不可以某天雇佣然后次日不雇佣，是从s_i一直工作到t_i，无法按天购买，所以我们要考虑更加巧妙的网络流建模。

题解里面，引入了一个叫做一面对多面的概念。也就是，我们当前点的决策会影响多个限制条件的改变，这时候，我们就要对于这里面的一面下功夫。容易发现，这个一面指的是人，那么我们就考虑，一个人，他的流量就是1。（大概算是个套路吧……）
既然一个人是一个流量，容易想到，对于每一种志愿者，(s_i,t_i,c_i)，我们可以建立一条跨过[s_i,t_i]所有点的边，费用为c_i，不过容易发现，人数限制没有被满足。

形式化的，我们把上面的边表示为[s_i,t_i+1,inf,c_i]，既然1流量对应一个人，考虑用这个定义来实现人数限制。具体的操作是对于一个限制a_i，建立[i,i+1,INF-a_i,0]。
最后为了满足限制，建立S,T，建立[S,1,inf,0],[n+1,T,inf,0]（注意是n+1，因为第i条边的限制用[i,i+1]表示） 建模为何合理呢？
显然最大流是inf嘛，所以对于每一天，0花费的边只能流inf-a_i，剩下的就是志愿者边流。

这个套路叫做网络流里的补集转化，用一个inf-a_i来表达a_i的限制。

但是！
这个做法不重要，因为一般很难想，想出来一般也不是个对的。

我们考虑一个线性规划的做法
设x_i为需要的第i类志愿者，a_{i,j}表示第i天第j类志愿者能否工作，A_i表示每天需求的志愿者数量，我们可以列出一些不等式

\left\{ \begin{array}{l} a_{1,1}x_1+a_{1,2}x_2+...+a_{1,m}x_m\geq A_1 \\a_{2,1}x_1+a_{2,2}x_2+...+a_{2,m}x_m\geq A_2 \\a_{3,1}x_1+a_{3,2}x_2+...+a_{3,m}x_m\geq A_3 \\... \\a_{n,1}x_1+a_{n,2}x_2+...+a_{n,m}x_m\geq A_n \\ \forall i\ \ x_i \geq 0 \end{array} \right.

题目要求的是Min\ z=\sum_{i=1}^m C_i\times x_i

线性规划转对偶确实可以快速（？）的解决这个题，迭代就行了，但是看不懂题解，我们采用一种简单的方式。
并且由于上面这个方程组太难了，所以我们利用样例来模拟这个过程
来弄一弄样例的方程组

\left\{ \begin{array}{l} x_1\geq 2\\ x_1+x_2\geq 3\\ x_3\geq 4 \end{array} \right.

（你看这个就比上面那个大东西优美多了）

不等式显然是没法建图之类的，所以考虑不等式转化为等式，设Y_i为第i天多招募的数量。

\left\{ \begin{array}{l} x_1-Y_1= 2\\ x_1+x_2-Y_2= 3\\ x_3-Y_3= 4 \end{array} \right.

显然，第零天和第四天都招募不到任何志愿者，然后我们把所有的柿子和他前一个式子相减，会得到这样的柿子。

\left\{ \begin{array}{l} x_1-Y_1=2\\ x_2+Y_1-Y_2=1\\ -x_1-x_2+x_3+Y_2-Y_3=1\\ -x_3+Y_3=-4 \end{array} \right.

虽然这个柿子不是很典型，不过我可以告诉大家一个结论，对于任意一个变量，在整个不等式组中，都会出现且仅出现两次，且系数一正一负

我们把所有的东西都移项到等式的右侧（当然你非要移动到左侧也是对的，毕竟网络流全边相反并不影响答案），按照这个柿子和他的性质，我们就可以建立网络流了。具体思路是：
我们把每个等式看成一个点，正数代表流入，负数代表流出，建立流量平衡。
对于右侧常数没地方能流给他，所以直接从起点终点连就行了。然后其他的由于都有两个变量，所以

然后最小费用最大流就可以了。
这个套路我们可以称之为线性规划转网络流，不过他的真实名字好像叫什么流量不等式之类的。
不重要了。
显然，下面这个方法相比于上面那个，思维难度低，不容易出错（移项还能移错那真是难为你了） 不过也不是很常用。

然后我们返回来再来看这玩意上树那个题。

给出一棵内向树，每条边有一定的权值，目标是所有的边权小于等于0，给出若干操作u_i,v_i,l_i,c_i，表示将u_i到v_i的路径上的边减1的权值需要c_i的费用，该操作共可执行l_i次。

由于是内向树，所以这个(u_i,v_i)不会出现穿过两个子树的情况，然后根据和上一个题一样的思路去列方程（太麻烦了这里就不写了）
然后，不难发现还是一个不等式，那么我们还是设一个额外清扫的次数Y，来变成等式，变成等式之后，考虑假设根节点有父亲，那么它需要清理的值是0，假设叶子节点有儿子，那么它需要清理的值是0。
用深度大的点的不等式减去深度小的点的等式。
然后建立超级源点汇点。
我们可以人为的设dep_u<dep_v，然后从树中提出一条链来，从这条链看建图，这条链建出的图就是整棵树该建的图了。
建图的方式没有任何变化，唯一需要注意的就是，上面那个题的志愿者可以请inf个，这里的化学药剂只能撒l_i次，因此需要把流量限制修改为l_i。

无他，仅此而已。

HDU3820

英语翻译大赛IX 题目大概说给一个n* m的格子，每个格子放金蛋或银蛋都会得到不同的价值，当然也可以不放，不过如果存在相邻的两个格子都是金蛋会损失价值g，都是银则损失s。问能得到的最大价值。

这个其实是普及小套路（好像是大套路来着），二分图染色+代价最小割

这种题，如果出现选或不选的话，就类似于最大权闭合子图的思路，考虑最小的代价，但是这个题出现了选A，选B，和不选，一个点着实是没法表示的，所以我们考虑拆点。

而这个题是棋盘上，棋盘上规划的惯性思路就是我先来一个黑白染色，设拆成的两部分为x,y，拆点之后就是x,x',y,y'。
建立[S,x,gold]，[x',T,silver]，建立[S,y,silver]，[y',T,gold]。拆点的必要操作要求我们必须要建立[x,x',inf],[y,y',inf]。对于相邻不相同，我们向相邻的两个x,y点建立[x,y',g]（两个都选金色）[y,x',s]（两个都选银色）
检验合理性，我们对于每一种割的方案，都可以找到他对应的合法实际意义。（比如说，割掉所有与T相连的就是x选金色，y选银色，割掉S,x与y,x'就是x和y都选银色，这里不细说了） 显然，求出的最小割就是付出的最小代价，价值和（金色和银色同时的价值和）-最小割就是答案了。

这种题其实没啥套路，就是想办法把最小的割在图上表示出来就是了。
能积累的地方大概就是，相邻代价这种东西可以先一波二分图染色，然后两个设计相反的状态。

HDU2435

忘了这个题有没有人讲过，好像应该是有。这里就是普及一下限制性最小割。

给你一个有向图,其中可以有一条边是无敌的,这条边可以是图中的边,也可以是自己任意加上去的图中没有的边,这条无敌的边不可以摧毁,让1和n的割最大。

首先可以n^2枚举然后最大流，显然T飞了。
考虑有这么一个题：给你一个图，求删除其中一条边之后最短路最大。
这个题的做法是枚举最短路上的边，然后检验答案（显然是正确的）

这个题的思路相同，最小割之后，原图被分为了两个集合A,B，只需要枚举之间的边即可。
这个题直接就这么做是可以通过的，不过有一种更快的方法，就是把残量网路记下来，每次把你要求的边的流量变成inf然后再流一次就行，可以节省一些复杂度。
不过数据范围比较小就没必要了。

HDU4322

如果孩子i的欢乐值大于$B[i]$，那么他才是开心的。能否有一种分配方案，让所有孩子都开心。 这个题难就难在，想到他是个费用流就费老劲了，反正我是想不到。 我直接把建模抄写一遍，估计就是个奇思妙想题，也没啥思考逻辑。 首先我们奇思妙想：对于多余的糖果或者是不被喜欢的糖果，他们的本质效益都是一样的，所以我们在建图的时候，不考虑多余的糖果。 - 对于糖果$j$，$[S,j,1,0]

具体来说，如果k|B[i]，那么说明，花费\frac {B[i]}{k}个喜爱的糖果就可以让他开心，这个时候的图是好建的。为[N+i,T,\frac {B[i]}{k},k]
然后剩下B\%k!=0的他还可能会拿最喜欢的糖果，所以额外添加一个[N+i,T,1,B\%k]

那么说到这里，大家应该就明白为什么这里需要用费用流了。
前面提到，我们要让尽可能多的糖果发挥“被喜爱糖果”的效益，然后剩下的糖果就本质相同，一个一个送就行。
而此时进行最大费用最大流，尽可能地保证了“祖国的一块砖”搬到最需要他的地方，他能填的多就填的尽量多。

然后这个题就套用最大费用最大流就直接做完了。
似乎题解区有人担心当B[i]\%k==1的时候，其实多余的这个糖果也是和其他糖果本质相同了，需不需要特判出来。其实不需要，因为这时候你的费用都是1了，肯定如果填了也是最后填的，无伤大雅，无非是帮你把后面的部分提前做了一点罢了。

最大流结束之后，看一下残量网络上剩下了多上糖果。然后贪心地一个一个填即可。

这个题我们可以学到：未必什么度的限制一定使用流量限制，也可以分个类，然后转化成利用费用限制。
私以为这个题出的特别好。

HDU3987

这个题应该讲过无数次了，由于是讲套路嘛，所以这里复习一下。 不上链接了，就是求最小割的最小割边数。

这个题是经典套路，不过我也不太会证明，感觉上是对的就是对的吧。
跑一个最小割，遍历所有正向边，如果他是满流的，则让他在残量网络的流量+1，如果没有满流，则残量网络流量变为inf，再次最大流就是答案。

还有一个方法，题解说是比较经典的方法，但我着实是觉得有些神器，令所有边的边权都为原来的边权w变为w\times (E+1)+1，然后再最后的时候让最大流对E+1去余数即可，据说是同时跑了两遍最大流，看起来也很有同时跑两遍的意思，不过感觉没写过还是很诡异，就稍微介绍一下吧2333

HDU4307

新科技
名词释义：transposition，转置矩阵。矩阵将行和列交换得到的矩阵，显然，矩阵的行列式不变。

这个大概是个新科技，以前看到过，但是没敢学，不过现在我觉得在这里讲一下大体是不过分的（真的不过分嘛？如果那啥的话就不讲这个题了吧..）

【前置知识】

最大流可以用来求解以下函数的最小值

f=\sum_{i=1}^n x_ia_i+\sum_{i=1}^n(1-x_i)b_i+\sum_i^n\sum_j^nx_i(1-x_j)c_{ij}(x_i\in{0,1})

因为我是一个普普通通的小白兔，我很难和你解释他的具体意义。
首先x_i只有两种取值，所以我们可以按照x_i最终的取值划分为两个集合，两个集合分别代表了一个取值a_i,b_i，其中如果x_i=1,x_j=0就会导致一个额外的代价c_{ij}。
经我这么一说，想必大家看这个柿子也稍微亲切一些了。

表达式中有三项，我们考虑建立源汇，然后最小割，我们用三种割边来表示三项。
考虑第一个，当x_i=1的时候，产生a_i的代价，将这条边设为[i,T,a_i]，此时物理意义是割掉i,T，保留S,i时，意味着选取1
考虑第二个，当x_i=0的时候，产生b_i的代价，将这条边设为[S,i,b_i]，物理意义类上 最后是x_i=1,x_j=0，产生c_{ij}的代价，此时建立[i,j,c_{ij}]，结合上面两个物理意义，容易发现，当满足条件的时候存在流S-i-j-T，符合条件。
然后直接最小割，就可以求得答案了。

那么这个题，我们先把矩阵乘法展开。

D=\sum_{i=1}^N((\sum_{j=1}^N a_j\times b_{ji}-c_i)\times a_i

这个柿子和上面那个表达式并没有什么关系，但不影响我们化简的热情。

=\sum_{i=1}^N\sum_{j=1}^N a_i a_j b_{ij}-\sum_{i=1}^N a_ic_i

然后强行配凑，想办法让a_ia_j的取值可以在一个1一个0的情况下可以影响答案

=\sum_{i=1}^N\sum_{j=1}^Nb_{ij}-\sum_{i=1}^N\sum_{j=1}^N(1-a_ia_j)\times b_{ij}-\sum_{i=1}^Na_ic_i

然后我们考虑a的取值对于原式的影响，发现了一个1-a_ia_j，题解表示这里是个套路，可以把它的贡献直接拆成两部分，即a_i=0和a_i=1,a_j=0，妙绝妙绝！！

=\sum_{i=1}^N\sum_{j=1}^Nb_{ij}-(\sum_{i=1}^N\sum_{j=1}^N[a_i=0]b_{ij}+\sum_i\sum_j[a_i=1,a_j=0]b_{ij}+\sum_{i=1}[a_i=1]c_i)

然后我们就知道了，取值为1，贡献为c_i，取值为0，贡献为\sum b_{ij}，可以预处理，中间那一项也符合上面的柿子。完美解决！

POJ2175

超级英文大赛
一个城市有n座建筑物，每个建筑物里面有一些人，为了在战争爆发时这些人都可以避难，城市里面建了m座避难所。每座避难所只能容纳有限人数。给出每个建筑物和避难所的坐标（题目要求距离为曼哈顿距离+1）。现在给你一种避难方案，问这种方案是否为最优方案，如果不是，请输出一种比当前更优的方案（不一定最优）

这个题就是八个字，难者不会会者不难
此题建模为最小费用的话会TLE，因为变数为O(nm)，别问为什么，问就是调了好久才发现复杂度本来就过不去。

不过这道题确确实实就是费用流没有问题。
不过需要一个定理：一个费用流的是最小费用流的充要条件是这个费用流的残量网络上没有负环
然后你暴力建图，按照他的方案进行增广，判断是否有负环，没有则意味着当前方案为最优方案，如果有负环，你既可以暴力KM增广一次，也可以沿着负圈把流量增加1，这样肯定是更优的方案。

POJ3680

板子题，考验速度的时候又到了！
给定若干的区间(a_i,b_i,c_i)，表示把(a_i,b_i)区间覆盖一次的权值为c_i，问每个点点被覆盖次数不超过k的最大权重。

这个题没啥逻辑，就是老套建图一波就行。
把数轴上每个数作为一个点。

不过我把这个题选进来是因为，最大费用问题有的时候需要费用取反，变成最小费用来做，但是有负边出现负环之类的就不太好了，为了处理这种问题，我们重新把原始对偶算法拎出来说一遍。

这里我们就不证明算法原理了，我们就说一下算法流程了（背代码就行，感性理解即可）
每次我们SPFA结束之后，我们记一个数组h为上次增广得到的累计答案。也就是说

SPFA();
for(int i=1;i<=n;i++){
    h[i]+=dist[i];
}

然后下一次增广的时候，把判断条件更改为

if(edge[i].f&&dist[v]>dist[u]+edge[i].w+h[u]-h[v]){
    dist[v]=dist[u]+edge[i].w+h[u]-h[v];
}

而此时每次增广的结果也不是dist[n]，而是更新之后的h[n]

具体为啥这样可以处理负边权我也忘的差不多了，反正正确性肯定是对的。

不过一般这东西也用不大到emmm，除非避免不了负边权。
可能证明需要线性规划转对偶吧，不过OI并不需要证明，能用就行（

最大密度子图

翻了半天，没翻到一道最大密度子图的题（边数与点数的比值最大），我估计是太非了，不过不记录一下总归是不好的。

假设答案为k，那么就是选出一个合适的点集V和边集E，让E-kV最大。显然有限制，选择一条边，必然选择他的两个端点。
建图：以原图的边作为左侧顶点u，[S,u,1]，原图的边作为右侧顶点，[v,T,-k]，然后转化成最大权闭合子图。
二分k即可。
如果是负的说明答案偏大了。

SGU438

这是啥OJ啊……完全不认识啊。

有一条河，河上有m个点，n人个人可以借助点跳到对岸（不同人不可以同时站在同一个点上），已知河的宽度M，点的坐标y，人的跳跃最大距离D（所有人都是克隆的，他们的最大跳跃距离一样），河的宽度和人数，问所有人是否可以跳到对岸，如果可以，求出这一大堆人跑到对岸的最小时间。

显然，时间上限为n+m，因为最差的一个人如果能跳到对岸，他可以把m个点都踩一遍，花费的时间为m+1，此时，第二个人可以重复第一个人的选择，此时有n-1个人重复这个过程，而每个人都比上一个人晚1个单位时间，因此，最劣时间为n-1+m+1=n+m

首先，我们预处理两两之间的距离是否小于等于人的跳跃距离D，需要注意的是，我们需要从左岸跳到点上，再从点跳到右岸上，所以也需要处理哪些坐标y\leq D以及y+D\geq M

然后神器的地方就来了，我们按照时间拆点！
记录i点t时刻的状态为(i,t)，注意到，当t=1的时候，一定是左岸跳过来的，可以建立[S,i,1]，不需要考虑他从哪个其他点跳过来，因此，我们从t=2开始枚举，对于合法的建立[(i,t-1),(j,t),1]

发现每个点能占的人只有一个，所以拆点，额外维护一下流量限制，每次只能流过一个人。

不过，发现这里的点全连起来的话有1e8条边，不过这个题没有卡。
可以尝试判断一下，容易发现，如果连边特别多的话，在河里经过的点应该不会特别多，所以可以考虑随机一个阈值，只连距离差在阈值内的边。
口胡的啊，感觉上由于连的特别多，所以具体连哪些对于答案的影响不大2333

SPOJ839

已知一些点的标号，标号大小为[0,2^{31}-1]，已知一些其他点，这些点的标号可以由你自由决定。
已知一些边，每条边的边权，为他两段点的点的标号异或值，你现在可以钦定这些点的标号（标号可以重复），求边权和最小。

这个题是异或和最小割的联动，显然，每一位互不干扰，转变为标号取0/1，然后求取最小值。
对于标号为1的点建立[S,u,inf]，对于标号为0的建立[v,T,inf]，显然他们的标号已经明确了，无法割掉。
对于原图相连的边，连边，容量为1,割掉这条边的意义就是两个端点一个是0，一个是1。

跑完最大流后，分成的两个集合，一个是1集合，一个是0集合，判断每个点所在的集合，输出即可。