最近一直在做网络流相关，于是都放上来了= =

BZOJ2127happiness：最小割

BZOJ3144切糕：最小割

BZOJ1497最大获利：胡BT论文题，裸最大权闭合子图。

BZOJ1443游戏Game：首先黑白染色构二分图，然后二分图中所有不一定在最大匹配中的点就是所求的答案。证明之类的细节详见CYB2015年论文

BZOJ2229最小割：图中的最小割两两不相交，然后n次最小割就可以了。

BZOJ2039employ人员雇佣：最小割

BZOJ2150部落战争：最小路径覆盖，网络流可以拆入点出点，S往出点连1，入点往T连1，中间的边INF，用点数-C[S,T]。或者直接Hungary

SPOJ Optimal Marks (OPTM)：胡BT论文题，按位跑网络流

BZOJ1066蜥蜴：最大流

BZOJ1433假期的宿舍：被模糊不清的题意坑了n次，而且^跟＾还有区别= =真心caodan。裸的二分图匹配，我用网络流写的= =

BZOJ1797Mincut最小割：貌似是跑一遍最小割，然后再残量网络中跑一遍强连通分量。设这条边的两端为u和v，如果这条边满流而且u和S在同一强连通分量里面且v和T在同一强连通分量里面就说明这条边必须割（试着给这条边增大流量限制显见）。如果这条边满流而且u和v不在同一强连通分量里面就说明这条边可以割。（真心不会证，网上也没什么好的证明= =跟duyege想了好久也是伪证）

BZOJ1266上学路线route：建最短路图然后跑最小割= =（然后这题时限caodan我换了几种姿势始终跑不过= =不知为何感觉我的dinic就是要比别人常数大）

BZOJ3504危桥：结论题，网上的题解都是些什么：“如果直接S连a1、b1，a2、b2连T，可能会a1流到b2、b1流到a2，所以要将起点换成b2，终点换成b1再跑一遍看两次是不是都是满流”，看上去好像“显而易见”一样，靠谱的证明一个都没有TATQAQ2333。

BZOJ1412狼和羊的故事：最小割

BZOJ1305跳舞dance：二分答案，拆点，给连坏边的点加上限制k，所有二分图中的边权为1，然后跑最大流= =

BZOJ1189紧急疏散：对于门按时间拆点，如果空地上这个人可以走到这个门就往这个门的那个时候连边，二分时间后每个门的当前时间t往t+1连INF。

BZOJ1822 Frozen Nova 冷冻波：建图很水，暴力连边然后二分答案跑网络流，但是计算几何真心caodan，而且貌似如果巫妖和小精灵与树相切是可以打到的。。。

BZOJ2756奇怪的游戏：显然如果n*m为偶数并且黑白染色后黑格之和不等于白格之和则无解，还有n*m为奇数并且黑白染色后黑格之和减去白格之和比最大值要小也是无解的。否则将图重建成二分图，然后二分答案网络流验证答案。如果学我的dinic不敢加优化会一直T一直T一直T= =

BZOJ1143祭祀：果然最近太颓了么= =一直没有看出来。传递闭包+最长反链（即最小链覆盖，即总点数-拆点后可达两点连边的二分图匹配数，YY可证）

为了方便，一条边的流量fi和费用vi用{fi,vi}表示

BZOJ1834网络扩容：第一问水过，第二问在残量网络上再给原图每条边复制一条流量INF、费用不变的边，残量网络无费用。

BZOJ1221软件开发：费用流，理解这么久我真是废到一定境界了，但确实感觉费用流比最小割的题目要caodan些= =。每个点拆成xi和yi，分别代表第i天的好毛巾和没洗毛巾，则S往xi连{ni,0}，S往yi连{INF,f}，yi往T连{ni,0}，xi往xi+1连{INF,0}，xi往y(i+a+1)连{INF,fa}，xi往y(i+b+1)连{INF,fb}，然后跑一遍。

BZOJ2661连连看：费用流。好神（keng）的题，看上去是一般图最大权匹配，实际上测试了一下才知道是二分图= =然后就黑白染色，暴力建图跑了。。（补：后来跑了一下大数据，然后这性质就果断不成立了，网上的什么拆点的如果碰到这种奇环也貌似是会挂的= =出题人sxbk）

BZOJ2424订货：费用流：拆点都不需要，很水的建图。

BZOJ2597剪刀石头布：费用流：确实很经典的题，很屌的建图。设每个点胜的场数为d[i]，则ans=C(n,3)-ΣC(d[i],2)，自行脑补。。然后化下式子变成C(n,3)+C(n,2)/2-Σd[i]^2/2，所以就对每个比赛建个点并且向T连{1,0}的边，每个点向它可能会胜利的比赛连{1,0}，S向每个点连{1,1}、{1,3}、{1,5}……这样可以保证是d[x]^2，然后跑费用流结果就是Σd[i]^2。

BZOJ1927星际竞速：费用流，最小权值路径覆盖。想了好久真是羞耻，就是拆点成Ui、Vi之后S往Ui连{1,0}，S往Vi连{1,Ai}，Vi往T连{1,0}，然后原图中的边i->j,w就连Ai往Bj连{1,w}，然后直接跑。

然后除了两个wa了n久的坑等着填，还有单纯性、zkw费用流什么的没学，网络流相关的东西就先搞到这里了。

现在貌似没什么很多时间了= =接下来是背堆模板？

算了感觉费用流的比例有点不太和谐，在颓废一个晚上算了= =应该不会拖进度吧。。。

不管了接着更，话说晚上状态真心不好：

BZOJ1930吃豆豆：看上去很裸，但是一来卡内存，二来卡时间，如果暴力建边会有n^2规模。（madan HZWER把把暴力建边的代码放到博客里面了，搞得我还一直以为这种暴力没人卡的。。。）反正就是要加优化：原来是对于每个点拆点然后流量限制都是1，但是现在允许一个点被走两次，但其中只算一次的豆豆，然后如果存在三个点a->b->c则a不往c连边，这样就可以跑出来了。这个正确性还算比较显然吧。。。

BZOJ1877晨跑：裸建图费用流

BZOJ3171循环格：反正每个点的入度都要为1，所以拆点，每两个相邻点相连，然后如果这条边原图中存在则费用为0否则为1，然后每个出点往T连1。

BZOJ2245工作安排：裸建图，一开始看错题了真是羞耻。。

BZOJ1070修车：把技术人员按倒数第几修的车拆点，然后连边跑跑跑！

BZOJ2879美食节：真心屌！虽然题目意思跟上题一毛一样，但是数据扩大了n倍，于是考虑优化连边，如果一个厨师倒数第k个还没流就不可能会流倒数第k+1个，于是动态连边，如果k满流了就建k+1的边。

BZOJ1565植物大战僵尸：最大权闭合子图乱入！很容易看出来是这个模型。同时还要注意有的点永远到不了，所以要先拓扑排序搞一波。

这次是真的不更了！