Mato is No.1

考虑这样一种网络流问题：需要对同一个图求多次最大流。则在每次求最大流之前，需要将所有边的容量全部恢复到初始值（求最大流的过程中，边的容量f值被改变了）。不过这还不算最猥琐的，有的时候，我们需要在每次求最大流之前都删去图中的一些点或一些边，或者改变某些原有的边的容量，特别是需要删点或删边的情况爆难搞。因为，一般的边表中边类型定义如下：
表示这条边起点为a，终点为b，容量为f，邻接边（就是下一条起点为a的边）的编号为next。
如果要求多次最大流，那么在每次求最大流之前就要把所有边的容量恢复到初始值，解决方法是引入一个“初始容量”域fs，在这条边刚刚被加入的时候将它的fs值和f值都设为初始给它的容量，在恢复时，只要将所有边的f值恢复到fs即可。若要改变边容量，则将该边的fs值和f值都设为改变后的容量即可。

下面来分析需要删边或删点的情况。在这种情况下，如果采用只有next的单向链表，则删除时next域极难处理，而且，在一般的边表中，还设立了表头hd，hd[a]表示边表中起点为a的第一条边的编号。因此，若删除的边<a, b, f>是起点为a的第一条边，还会影响hd[a]的值，使情况变得更为复杂。因此，必须采用双向链表！还记得Dancing Link么？边表其实也可以搞成Dancing Link，方法如下：
设图中有N个点，M条边（注意，这M条边只包括正向边，不包括反向边。由于每条正向边<a, b, f>都对应一条反向边<b, a, 0>，因此边表中边的数目其实是M+M）。首先把边表ed的0~N这(N+1)个位置（下标）空出来，作表头（表头不是边，因此在遍历边的时候不会遍历到它们）。其中，ed[0]为总表头，用于遍历ed[1..N]中每个未被删去的点；ed[1..N]为单点表头，ed[i]用来遍历图中所有以i为起点的边（和DLX中的二维DL惊人相似）。然后，若N为偶数，则空一个位置（也就是将ed[N+1]丢弃不用），这是因为我们在增广过程中需要引用到一条边对应的逆向边（正向边对应反向边，反向边对应正向边），一般认为编号为p的边对应的逆向边是p ^ 1，这样，就要求图中所有正向边的编号都是偶数，所有反向边的编号都是奇数（否则会造成混乱）。因此当N为偶数时，(N+1)为奇数，不能放置第一条正向边，需要从ed[N+2]开始放置正向边。若N为奇数则不用空位。
接下来就是边类型了。在这里，边类型一共需要包括6个域：a, b, fs, f, pre, next，表示这条边起点为a，终点为b，初始容量为fs，当前容量为f，上一条起点为a的边编号为pre，下一条起点为a的边编号为next。注意，和DL一样，整个链表是循环的，也就是我们认为表中最后一条起点为a的边的下一条邻接边编号就是a（表头），同样，a的上一条邻接边也就是这条边。
接下来就是几个重要过程了。
（1）初始化表头：
这里n是图中的点数（相当于N），m是边的编号指针（相当于DLX中的nodes）
（2）添加新边：
这个和DLX类似，不解释了囧……

最后进入最核心的部分——到底如何处理删边或删点？有了DL型边表就爆好搞了：删去一条边，只要直接删去该边在DL中的位置即可：
恢复一条已删去的边：
需要删点的情况类似，对单点表头处理即可。

【具体题目】PKU1815
这题就是求有向图的字典序最小的最小点割集问题，方法是先求出最小点连通度（有关最小点连通度的求法见图的连通度问题的求法），然后按编号递增顺序枚举每个点，若删去该点（其实是删去建成的新图中该点i'到该点附加点i''之间的边）后图的最小点连通度减小，则应删去该点，否则不应删去该点。删去后，继续枚举下一个点，直到求出点割集为止。
注意，本题只有删边，没有删点，因此总表头可以不需要，直接从ed[0]开始作单点表头。此时，关于是否空位就刚好反过来了：如果N是奇数就要空位，N是偶数不空位（不过这题里由于建出的网络流图中有2*N0个结点，总是偶数，可以不管，不过本沙茶还是管这个了）。

代码（神犇不要鄙视）：