考慮這樣一種網(wǎng)絡(luò)流問(wèn)題：需要對(duì)同一個(gè)圖求多次最大流。則在每次求最大流之前，需要將所有邊的容量全部恢復(fù)到初始值（求最大流的過(guò)程中，邊的容量f值被改變了）。不過(guò)這還不算最猥瑣的，有的時(shí)候，我們需要在每次求最大流之前都刪去圖中的一些點(diǎn)或一些邊，或者改變某些原有的邊的容量，特別是需要?jiǎng)h點(diǎn)或刪邊的情況爆難搞。因?yàn)椋话愕倪叡碇羞咁?lèi)型定義如下：
struct edge {
int a, b, f, next;
} ed[MAXM + MAXM];
表示這條邊起點(diǎn)為a，終點(diǎn)為b，容量為f，鄰接邊（就是下一條起點(diǎn)為a的邊）的編號(hào)為next。
如果要求多次最大流，那么在每次求最大流之前就要把所有邊的容量恢復(fù)到初始值，解決方法是引入一個(gè)“初始容量”域fs，在這條邊剛剛被加入的時(shí)候?qū)⑺膄s值和f值都設(shè)為初始給它的容量，在恢復(fù)時(shí)，只要將所有邊的f值恢復(fù)到fs即可。若要改變邊容量，則將該邊的fs值和f值都設(shè)為改變后的容量即可。
下面來(lái)分析需要?jiǎng)h邊或刪點(diǎn)的情況。在這種情況下，如果采用只有next的單向鏈表，則刪除時(shí)next域極難處理，而且，在一般的邊表中，還設(shè)立了表頭hd，hd[a]表示邊表中起點(diǎn)為a的第一條邊的編號(hào)。因此，若刪除的邊<a, b, f>是起點(diǎn)為a的第一條邊，還會(huì)影響hd[a]的值，使情況變得更為復(fù)雜。因此，必須采用雙向鏈表！還記得Dancing Link么？邊表其實(shí)也可以搞成Dancing Link，方法如下：
設(shè)圖中有N個(gè)點(diǎn)，M條邊（注意，這M條邊只包括正向邊，不包括反向邊。由于每條正向邊<a, b, f>都對(duì)應(yīng)一條反向邊<b, a, 0>，因此邊表中邊的數(shù)目其實(shí)是M+M）。首先把邊表ed的0~N這(N+1)個(gè)位置（下標(biāo)）空出來(lái)，作表頭（表頭不是邊，因此在遍歷邊的時(shí)候不會(huì)遍歷到它們）。其中，ed[0]為總表頭，用于遍歷ed[1..N]中每個(gè)未被刪去的點(diǎn)；ed[1..N]為單點(diǎn)表頭，ed[i]用來(lái)遍歷圖中所有以i為起點(diǎn)的邊（和DLX中的二維DL驚人相似）。然后，若N為偶數(shù)，則空一個(gè)位置（也就是將ed[N+1]丟棄不用），這是因?yàn)槲覀冊(cè)谠鰪V過(guò)程中需要引用到一條邊對(duì)應(yīng)的逆向邊（正向邊對(duì)應(yīng)反向邊，反向邊對(duì)應(yīng)正向邊），一般認(rèn)為編號(hào)為p的邊對(duì)應(yīng)的逆向邊是p ^ 1，這樣，就要求圖中所有正向邊的編號(hào)都是偶數(shù)，所有反向邊的編號(hào)都是奇數(shù)（否則會(huì)造成混亂）。因此當(dāng)N為偶數(shù)時(shí)，(N+1)為奇數(shù)，不能放置第一條正向邊，需要從ed[N+2]開(kāi)始放置正向邊。若N為奇數(shù)則不用空位。
接下來(lái)就是邊類(lèi)型了。在這里，邊類(lèi)型一共需要包括6個(gè)域：a, b, fs, f, pre, next，表示這條邊起點(diǎn)為a，終點(diǎn)為b，初始容量為fs，當(dāng)前容量為f，上一條起點(diǎn)為a的邊編號(hào)為pre，下一條起點(diǎn)為a的邊編號(hào)為next。注意，和DL一樣，整個(gè)鏈表是循環(huán)的，也就是我們認(rèn)為表中最后一條起點(diǎn)為a的邊的下一條鄰接邊編號(hào)就是a（表頭），同樣，a的上一條鄰接邊也就是這條邊。
struct edge {
int a, b, fs, f, pre, next;
} ed[MAXM + MAXM];
接下來(lái)就是幾個(gè)重要過(guò)程了。
（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 + 1; else m = n + 2;
}
這里n是圖中的點(diǎn)數(shù)（相當(dāng)于N），m是邊的編號(hào)指針（相當(dāng)于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++;
}
這個(gè)和DLX類(lèi)似，不解釋了囧……
最后進(jìn)入最核心的部分——到底如何處理刪邊或刪點(diǎn)？有了DL型邊表就爆好搞了：刪去一條邊，只要直接刪去該邊在DL中的位置即可：
void deledge(int No)
{
ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
}
恢復(fù)一條已刪去的邊：
void resuedge(int No)
{
ed[ed[No].pre].next = ed[ed[No].next].pre = No;
}
需要?jiǎng)h點(diǎn)的情況類(lèi)似，對(duì)單點(diǎn)表頭處理即可。
【具體題目】
PKU1815這題就是求有向圖的字典序最小的最小點(diǎn)割集問(wèn)題，方法是先求出最小點(diǎn)連通度（有關(guān)最小點(diǎn)連通度的求法見(jiàn)
圖的連通度問(wèn)題的求法），然后按編號(hào)遞增順序枚舉每個(gè)點(diǎn)，若刪去該點(diǎn)（其實(shí)是刪去建成的新圖中該點(diǎn)i'到該點(diǎn)附加點(diǎn)i''之間的邊）后圖的最小點(diǎn)連通度減小，則應(yīng)刪去該點(diǎn)，否則不應(yīng)刪去該點(diǎn)。刪去后，繼續(xù)枚舉下一個(gè)點(diǎn)，直到求出點(diǎn)割集為止。
注意，本題只有刪邊，沒(méi)有刪點(diǎn)，因此總表頭可以不需要，直接從ed[0]開(kāi)始作單點(diǎn)表頭。此時(shí)，關(guān)于是否空位就剛好反過(guò)來(lái)了：如果N是奇數(shù)就要空位，N是偶數(shù)不空位（不過(guò)這題里由于建出的網(wǎng)絡(luò)流圖中有2*N0個(gè)結(jié)點(diǎn)，總是偶數(shù)，可以不管，不過(guò)本沙茶還是管這個(gè)了）。
代碼（神犇不要鄙視）：
#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 + 1; else 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 = 0; while (dfs()) ; int f_ = flow;
if (!flow) {reslen = -1; return;}
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 = 0; while (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;
}