考虑这样一种网络流问题:需要对同一个图求多次最大流。则在每次求最大流之前,需要将所有边的容量全部恢复到初始值(求最大流的过程中,边的容量f值被改变了)。不过这还不算最猥琐的,有的时候,我们需要在每次求最大流之前都删去图中的一些点或一些边,或者改变某些原有的边的容量,特别是需要删点或删边的情况爆难搞。因为,一般的边表中边类型定义如下:
struct edge {
        
int a, b, f, next;
} ed[MAXM 
+ MAXM];
表示这条边起点为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的上一条邻接边也就是这条边。
struct edge {
    
int a, b, fs, f, pre, next;
} ed[MAXM 
+ MAXM];
接下来就是几个重要过程了。
(1)初始化表头:
void init_d()
{
    re1(i, n) {ed[i].a 
= i; ed[i].b = -1; ed[i].f = 0; ed[i].pre = ed[i].next = i;}
    
if (n % 2) m = n + 1else m = n + 2;
}
这里n是图中的点数(相当于N),m是边的编号指针(相当于DLX中的nodes)
(2)添加新边:
void add_edge(int a, int b, int f)
{
    ed[m].a 
= a; ed[m].b = b; ed[m].fs = ed[m].f = f; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a 
= b; ed[m].b = a; ed[m].fs = ed[m].f = 0; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
这个和DLX类似,不解释了囧……

最后进入最核心的部分——到底如何处理删边或删点?有了DL型边表就爆好搞了:删去一条边,只要直接删去该边在DL中的位置即可:
void deledge(int No)
{
    ed[ed[No].pre].next 
= ed[No].next; ed[ed[No].next].pre = ed[No].pre;
}
恢复一条已删去的边:
void resuedge(int No)
{
    ed[ed[No].pre].next 
= ed[ed[No].next].pre = No;
}
需要删点的情况类似,对单点表头处理即可。

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

代码(神犇不要鄙视):
#include <iostream>
#include 
<stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 501, MAXM = 100000, INF = ~0U >> 2;
struct edge {
    
int a, b, fs, f, pre, next;
} ed[MAXM 
+ MAXM];
int n0, n, m = 0, s, t, start[MAXN], pr[MAXN], hs[MAXN], lev[MAXN], q[MAXN], now, flow, reslen = 0, res[MAXN];
bool vst[MAXN];
void init_d()
{
    re(i, n) {ed[i].a 
= i; ed[i].b = -1; ed[i].f = 0; ed[i].pre = ed[i].next = i;}
    
if (n % 2) m = n + 1else m = n;
}
void add_edge(int a, int b, int f)
{
    ed[m].a 
= a; ed[m].b = b; ed[m].fs = ed[m].f = f; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a 
= b; ed[m].b = a; ed[m].fs = ed[m].f = 0; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void init()
{
    
int x;
    scanf(
"%d%d%d"&n0, &s, &t);
    n 
= n0 << 1; s--; t += n0 - 1; init_d();
    re(i, n0) re(j, n0) {
        scanf(
"%d"&x);
        
if (i == j) {
            
if (i == s || i == t - n0) add_edge(i, i + n0, INF); else add_edge(i, i + n0, 1);
        } 
else if (x) add_edge(i + n0, j, INF);
    }
}
void aug()
{
    
int z = hs[t], i = t, p; flow += z;
    
while (i != s) {
        hs[i] 
-= z; p = pr[i]; ed[p].f -= z; ed[p ^ 1].f += z; i = ed[p].a;
        
if (!ed[p].f) now = i;
    }
}
bool dfs()
{
    re(i, n) vst[i] 
= 0; vst[s] = 1; q[0= s; lev[s] = 0;
    
int i, j, f0;
    
for (int front=0, rear=0; front<=rear; front++) {
        i 
= q[front];
        
for (int p=ed[i].next; p != i; p=ed[p].next) if (ed[p].f) {
            j 
= ed[p].b;
            
if (!vst[j]) {vst[j] = 1; q[++rear] = j; lev[j] = lev[i] + 1;}
        }
    }
    
if (!vst[t]) return 0;
    now 
= s; re(i, n) {start[i] = ed[i].next; vst[i] = 0;} hs[now] = INF;
    
bool fd;
    
while (!vst[s]) {
        
if (now == t) aug();
        fd 
= 0;
        
for (int p=start[now]; p != now; p=ed[p].next) {
            j 
= ed[p].b; f0 = ed[p].f;
            
if (lev[now] + 1 == lev[j] && !vst[j] && f0) {
                fd 
= 1; start[now] = pr[j] = p; hs[j] = hs[now] <= f0 ? hs[now] : f0; now = j; break;
            }
        }
        
if (!fd) {
            vst[now] 
= 1;
            
if (now != s) now = ed[pr[now]].a;
        }
    }
    
return 1;
}
void deledge(int No)
{
    ed[ed[No].pre].next 
= ed[No].next; ed[ed[No].next].pre = ed[No].pre;
}
void resuedge(int No)
{
    ed[ed[No].pre].next 
= ed[ed[No].next].pre = No;
}
void resu_all()
{
    re(i, n) 
for (int p=ed[i].next; p != i; p=ed[p].next) ed[p].f = ed[p].fs;
}
void solve()
{
    flow 
= 0while (dfs()) ; int f_ = flow;
    
if (!flow) {reslen = -1return;}
    re(i, m) 
if (ed[i].a + n0 == ed[i].b && ed[i].a != s && ed[i].b != t) {
        deledge(i); deledge(i 
^ 1); resu_all();
        flow 
= 0while (dfs()) ;
        
if (flow < f_) {res[reslen++= ed[i].a + 1; f_--;} else {resuedge(i ^ 1); resuedge(i);}
    }
}
void pri()
{
    
if (reslen == -1) puts("0"); else if (reslen) {
        printf(
"%d\n", reslen);
        re(i, reslen 
- 1) printf("%d ", res[i]); printf("%d\n", res[reslen - 1]);
    } 
else puts("NO ANSWER!");
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理