网络流-最大流-费用流-个人总结

## 费用流速度受边数影响很大！ **看12月集训笔记** 介于我写的Dinic经常被卡，无奈，转写EK型Dinic。 个人认为，当图的深度比较浅时，这样会比较快；否则，还是多路增广较快 ```cpp int dfs(int x,int f) { if(x==T||!f) return f; for(ri &i=cur[x]; i; i=nx[i]) if(d[v[i]]+1==d[x]&&w[i]) { int t=dfs(v[i],min(f,w[i])); if(t) { w[i]-=t,w[i^1]+=t; return t; } } return 0; } int dinic() { int ans=0; while(bfs()) { memcpy(cur,head,sizeof head); int tmp=0; while((tmp=dfs(S,inf))) ans+=tmp; } return ans; } ```  ## 网络流记得建反边 # 边的cnt记得设为1 ## SPFA用STL的queue，动态大小 ## 方格取数问题 如何满足相邻的点只选取一个呢？对于这种多选一的问题（~~仿佛二分图一样~~）我们采用的时最小割： S->黑点，容量为点权 白点->T，容量为点权 每一个黑点->取该黑点会受到影响的白点，容量为inf 这样，如果ST联通，说明选择了相邻点，直到成为割才符合要求； 注意： 一定要在适当的位置改变n的大小，n在输入时为行数，在ISAP时为点数； ## 方格取数加强版 按照网格建立网络，每个点拆成入点和出点，入点向出点连$flow=1,cost=-val$的边（负数是为了把最大费用最大流改成最小费用最大流），再连$flow=inf,cost=0$的边，表示第二次经过； 然后每个点向右和下连inf的边，S向1，1连容量为K的边，n，n向T连边； ~~只能向右和下连边，不能四个方向，不然有负环，SPFA挂~~ ## [SCOI2007]修车 **注意到，一辆车排到了一个工人的第k个，这个工人一共要修n辆车，那么修理它的代价就是$time\times (n-k)$** 将m个工人拆成n个点，表示n个时间段； 将n个顾客连向$N\times M$个点，边权为修理时间×时间段，流量为1； 源点向N个顾客连边，流1费0；$N\times M$个工人点向汇点连边，流1费0； ## 平面图最大流等于对偶图的最短路 如图。  啥？你说如何区分源汇点？ 连一条原图S->T的边在最外面，有框出来一个新的平面为S，外面的为T  例题：狼抓兔子 但是不要被迷惑了，因为《狼抓兔子》的正反边权一样，但是遇到《海拔》这种题，正反边权不一样的情况，一定要画图，**好好确定边的方向**。 ## DAG最小代权路径覆盖 《星际竞速》 拆AB点，S向A连流1费0，B向T连流1费-a（代表不用瞬移到这里了），对于边$(u,v)$，连$(u_A,v_b)$流1费w（边权）。答案为$\sum a-$最小费用流（费用>=0就停止）。 **两部分不能选公共的：将公共的视为边，求独立集** **如何在网络流中强制某条边必须满流？可以跑“有上下界的”网络流；也可以把它的边权设为-inf** ------------- **利用自动的流量分配解决一类关于分配某种物资的问题**。  ## 网络流的有关矩阵的问题，都可以考虑二分染色 ### 网络流的流有速度（例如一个单位时间走一条边），或是在某个时刻加入流量限制。通常通过拆点来解决 [HNOI2007]紧急疏散：二分时间T，将每个点拆成T个点。 ## 两个集合的矛盾关系可以使用最小割建模 Google Code Jam 2014 Round2C 最大流->最小割->对偶图最短路。 Ski Resort N × M 的矩阵，每个点有高度。可以花 1 的代价将某点的高度提高 1。每个点可以到相邻的不比它高的点。求最小代价使 A 不能到 B。 这道题使用最小割的方法非常巧妙，想到了按高度拆点，但是没想到如何应用到最小割。  7是这个点，红点是它周围的点。 这样连，将高度差更大的的连在最底层，这样高度就形成了“或”的关系，只能选一个。 ```cpp for(ri i=1;i<=n;++i) for(ri j=1;j<=m;++j) { static int xx[]={0,-1,0,1},yy[]={1,0,-1,0}; static pii b[5]; int cnt=0; for(ri dir=0;dir<4;++dir) { int tx=i+xx[dir],ty=j+yy[dir]; if(tx<1||ty<1||tx>n||ty>m) continue; if(a[tx][ty]>=a[i][j]) b[++cnt]=mp(tx,ty); } if((i==Ax&&j==Ay)||(i==Bx&&j==By)) { for(ri o=1;o<=cnt;++o) adde(id[b[o].fi][b[o].se],id[i][j],inf); continue; } sort(b+1,b+1+cnt,[](const pii &x,const pii &y) { return a[x.fi][x.se]>a[y.fi][y.se]; }); int pre=id[i][j]; for(ri o=1;o<=cnt;++o) { adde(++tot,pre,a[b[o].fi][b[o].se]+1-a[i][j]); adde(id[b[o].fi][b[o].se],tot,inf); pre=tot; } } ``` ## 最小割可以解决的模型 每个点选或不选（01两种状态） 1. 每个点选01有代价。 2. 某两个选的不同有代价。 3. 若干个选的相同有代价。 这样建图： 在最小割中，与S相连表示不选，与T相连表示选。 对于3.，给每个集合新建一个点p，S向p连集合的代价，p向元素连inf，这表示集合里的元素都选的代价；再新建p'，向T连集合的代价，元素向p'连inf，表示都不选的代价。 对于2.，连接$(x,y)$表示x不选而y选的代价 对于1.，S向每个点连选的代价，每个点向T连不选的代价。 **网络流的一种套路：先假设所有都选，再扣除最少的**。 CEOI 2008 order 有 N 个工作，M 个机器，每种机器可以按次数租用或是买过来，每个工作需要使用一些机器，完成后可以获得收益。求最大获利。 如果没有租用，就是一个裸的最大权闭合子图，而且还是二分图。 租用相当于一个**违反代价**：物品 A 可以不依赖于物品 B，但需要付出一定代价。将机器于任务之间连的边容量设为租用代价即可。 ### SurroundingGame N × M 的矩阵，每个点有选择代价和控制收益。一个点被控制当且仅当它被选择或者它的邻居都被选择。 最小割思想建图的应用。 注意到我们有哪些选择？ 1.放弃收益 2.选择这个点 3.选择这个点周围的点 注意到最大权闭合子图很难处理“或”的关系，所以我们把3.变为：不选这个点且选择这个点周围的点，然后这样建图：  ### Boardpainting N × M 的棋盘，有些格子有棋子。每次可以拿走同行或同列中若干连续的棋子。求至少多少次操作可以拿走所有棋子。 默认每个点都独立消除。若上下相邻两个棋子都是竖着拿，得到 1 的收益，若左右相邻两个棋子都是横着拿，得到 1 的收益。**最大权闭合子图模型**。 ## 费用流 经典问题 **费用不为一次函数的问题** 拆边，用差分后的一次函数建边。 JSOI2009球队收益：一个常用Trick：先假设所有球队都输，然后用网络流调成赢。 **带下界的最小费用可行流问题** 如何在网络流中表示“区间加”的操作？ 方法一：类似于“志愿者招募”，我们可以把每个点穿成一串$(i,i+1)$，这样区间加就相当于$(R+1,L)$ 方法二：S向$[1,n]$连边，$(i,i+1)$，$[2,n+1]$向T连边。这样做的好处是可以通过限流来限制区间的选择数量。 **线性规划问题** 类比HNOI切糕，  ### 好题：[CTSC2009]移民站选址 横纵坐标无关。类比切糕的思想，每个B的坐标一定是A的坐标中的一个，这样$f(x,v)$就能处理出来了。然后解决B之间的贡献，可以在每条链上竖着连，这样最小割中间就能通过差分得到正确的贡献。 ### BZOJ 3716 题意是最大权闭合子图的裸题，但是如何建图？我想了数据结构建图很久，结果正解是：**用新的基底表示空间，模拟最大流** 变成每个守卫可以向xy坐标大的物品流流量，然后扫描线，每个守卫优先向y大于它的最小的物品连边。 # 网络流24题 ### 最长不下降子序列问题 emmmm这道题在思考的时候，想到了一个限制长度的方法：强制每个流必须从1进，从s出，中间的dp值严格+1，但是随后pass掉了这个做法，以为这样限制，可能不能选出最多的链。原来这个是可以证明最优解都可以转化为这样的形式，手玩几组就可以发现了。 ~~woc我TM调了半个小时结果发现我连边的时候没判断！！！我最近是怎么了不在状态~~ ### 最长k可重区间集问题 唔，好题，学到新姿势了。我们把端点离散化，然后用流k费0的边穿起来整条链，和ST也连起来，这样，对于线段$(l,r)$，连边$l\to r$表示如果选择这条边，那么经过$(l,r)$的流量都会-1。 ### 最长k可重线段集问题 这道题相比上一题的区别在于横坐标可能相同，这样就有负环了，我们当然可以直接判掉（贪心的加入），也可以**拆点，使负环拆散** -------------------- ### CF739E Gosha is hunting 网络流表示代价的方法：可以在一对点中连多条边，表示第1,2...次选择的代价 这道题还有数据结构和wqs二分的做法。