網(wǎng)絡(luò)流最讓人不能忍受的不是模板，而是建模！尤其是某些題目里面需要搞一段很長的預(yù)處理才能開始寫網(wǎng)絡(luò)流……
最大閉合子圖就是其中的一種。如果要求最大閉合子圖的有向圖里面有環(huán)就很囧了，因為在某些題目里（比如NOI2009的pvz），取點是有先后順序的，因此環(huán)中的點一個也取不了（有的題則不是這樣，子圖里的點可以一次全部取來，這時對于環(huán)就有兩種方案了：要么全取，要么一個不取，此時不用管環(huán)，直接進(jìn)入網(wǎng)絡(luò)流即可），不僅如此，根據(jù)閉合子圖的定義，如果一個點i可以到達(dá)一個點j（注，是“可以到達(dá)”點j，也就是從i到j(luò)有路徑），而點j屬于某個環(huán)，那么點i也不能取，因此在預(yù)處理中需要把點i也刪掉。以下將屬于某個環(huán)中的點成為“環(huán)點”，將可以到達(dá)環(huán)點的點稱為“環(huán)限制點”，這兩種點在預(yù)處理中都要刪除。
本沙茶以前用的一般方法是：先求圖的傳遞閉包，找出所有的環(huán)點（能夠到達(dá)自己的點），再從每個環(huán)點開始進(jìn)行逆向遍歷（將原圖所有邊反向，再遍歷），找到所有的環(huán)限制點。該方法的時間復(fù)雜度高達(dá)O(N
3)，且寫起來也爆麻煩。
其實，真正用于去環(huán)的最佳方法是拓?fù)渑判颍。。?br>
首先將原圖的所有邊反向，然后進(jìn)行拓?fù)渑判颍斜闅v到的點是保留下來的點，而沒有遍歷到的點就是環(huán)點或環(huán)限制點，需要刪除。
【證明：環(huán)點顯然是不可能被遍歷到的，而在反向后的新圖中，對于一個環(huán)限制點j，必然存在一個環(huán)點i能夠到達(dá)它，而i不能被遍歷到，故j也不能被遍歷到。除了這兩種點外，其它的點的所有前趨必然也都不是環(huán)點或環(huán)限制點（否則這些點就成了環(huán)限制點），因此只要入度為0（不存在前趨）的點能夠遍歷到，這些點也能夠遍歷到，而入度為0的點顯然能遍歷到，故這些點也能被遍歷到。證畢】
由于求反向圖和拓?fù)渑判蚨伎梢栽贠(M)時間內(nèi)完成，整個去環(huán)過程的時間復(fù)雜度就是O(M)的。
下面附上NOI2009 pvz代碼：（注意，本題的第9個點是一個超級大數(shù)據(jù)，最后建出來的網(wǎng)絡(luò)的邊數(shù)將會達(dá)到300000，故MAXM取150000，另外，本題必須使用Dinic，SAP會超）
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 602, MAXM = 150000, INF = ~0U >> 2;
struct link {
int kk;
link *next;
} *ed[MAXN], *ed2[MAXN];
struct edge {
int a, b, f, next;
edge () {}
edge (int _a, int _b, int _f): a(_a), b(_b), f(_f), next(-1) {}
} ed_[MAXM + MAXM];
int n, m = 0, s, t, sc[MAXN], hd[MAXN], tl[MAXN], st[MAXN], lev[MAXN], q[MAXN], hs[MAXN], pr[MAXN], ind[MAXN], now, res = 0;
bool vst[MAXN];
void init()
{
freopen("pvz.in", "r", stdin);
int n0, m0, A[20][30], num = 1, x, y, z;
scanf("%d%d", &n0, &m0);
re(i, n0) re(j, m0) A[i][j] = num++;
n = n0 * m0 + 2; s = 0; t = n - 1; memset(ed, 0, n << 2); memset(ed2, 0, n << 2);
re1(i, n - 2) {
scanf("%d%d", &sc[i], &num);
re(j, num) {
scanf("%d%d", &x, &y); z = A[x][y];
link *p1 = new link; p1->kk = i; p1->next = ed[z]; ed[z] = p1;
link *p2 = new link; p2->kk = z; p2->next = ed2[i]; ed2[i] = p2; ind[z]++;
}
}
re(i, n0) re2(j, 1, m0) {
z = A[i][j];
link *p1 = new link; p1->kk = z; p1->next = ed[z - 1]; ed[z - 1] = p1;
link *p2 = new link; p2->kk = z - 1; p2->next = ed2[z]; ed2[z] = p2; ind[z - 1]++;
}
fclose(stdin);
}
inline void add_edge(int a, int b, int f)
{
ed_[m] = edge(a, b, f);
if (hd[a] != -1) tl[a] = ed_[tl[a]].next = m++; else hd[a] = tl[a] = m++;
ed_[m] = edge(b, a, 0);
if (hd[b] != -1) tl[b] = ed_[tl[b]].next = m++; else hd[b] = tl[b] = m++;
}
void prepare()
{
int front = 0, rear = -1;
re1(i, n - 2) if (!ind[i]) {q[++rear] = i; vst[i] = 1;}
int i, j;
for (; front<=rear; front++) {
i = q[front];
for (link *p=ed2[i]; p; p=p->next) {
j = p->kk; ind[j]--;
if (!ind[j]) {vst[j] = 1; q[++rear] = j;}
}
}
memset(hd, -1, n << 2); memset(tl, -1, n << 2);
re1(i, n - 2) if (vst[i]) {
if (sc[i] > 0) {res += sc[i]; add_edge(s, i, sc[i]);}
if (sc[i] < 0) add_edge(i, t, -sc[i]);
}
re1(i, n - 2) if (vst[i]) for (link *p=ed[i]; p; p=p->next) {
j = p->kk;
if (vst[j]) add_edge(i, j, INF);
}
}
void aug()
{
int z = hs[t], i = t, p;
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;
}
res -= z;
}
bool dfs()
{
q[0] = s; memset(vst, 0, n); vst[s] = 1; lev[s] = 0;
int i, j, f0;
for (int front=0, rear=0; front<=rear; front++) {
i = q[front];
for (int p=hd[i]; p != -1; p=ed_[p].next) {
j = ed_[p].b; f0 = ed_[p].f;
if (!vst[j] && f0) {vst[j] = 1; lev[j] = lev[i] + 1; q[++rear] = j;}
}
}
if (!vst[t]) return 0;
now = s; hs[s] = INF; memset(vst, 0, n);
re(i, n) st[i] = hd[i];
bool ff;
while (!vst[s]) {
if (now == t) aug();
ff = 0;
for (int p=st[now]; p != -1; p=ed_[p].next) {
j = ed_[p].b; f0 = ed_[p].f;
if (lev[now] + 1 == lev[j] && !vst[j] && f0) {
st[now] = pr[j] = p; hs[j] = hs[now] <= f0 ? hs[now] : f0; now = j; ff = 1; break;
}
}
if (!ff) {
vst[now] = 1;
if (now != s) now = ed_[pr[now]].a;
}
}
return 1;
}
void solve()
{
while (dfs()) ;
}
void pri()
{
freopen("pvz.out", "w", stdout);
printf("%d\n", res);
fclose(stdout);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}