网络流最让人不能忍受的不是模板，而是建模！尤其是某些题目里面需要搞一段很长的预处理才能开始写网络流……
最大闭合子图就是其中的一种。如果要求最大闭合子图的有向图里面有环就很囧了，因为在某些题目里（比如NOI2009的pvz），取点是有先后顺序的，因此环中的点一个也取不了（有的题则不是这样，子图里的点可以一次全部取来，这时对于环就有两种方案了：要么全取，要么一个不取，此时不用管环，直接进入网络流即可），不仅如此，根据闭合子图的定义，如果一个点i可以到达一个点j（注，是“可以到达”点j，也就是从i到j有路径），而点j属于某个环，那么点i也不能取，因此在预处理中需要把点i也删掉。以下将属于某个环中的点成为“环点”，将可以到达环点的点称为“环限制点”，这两种点在预处理中都要删除。
本沙茶以前用的一般方法是：先求图的传递闭包，找出所有的环点（能够到达自己的点），再从每个环点开始进行逆向遍历（将原图所有边反向，再遍历），找到所有的环限制点。该方法的时间复杂度高达O(N
3)，且写起来也爆麻烦。
其实，真正用于去环的最佳方法是拓扑排序！！！
首先将原图的所有边反向，然后进行拓扑排序，所有遍历到的点是保留下来的点，而没有遍历到的点就是环点或环限制点，需要删除。
【证明：环点显然是不可能被遍历到的，而在反向后的新图中，对于一个环限制点j，必然存在一个环点i能够到达它，而i不能被遍历到，故j也不能被遍历到。除了这两种点外，其它的点的所有前趋必然也都不是环点或环限制点（否则这些点就成了环限制点），因此只要入度为0（不存在前趋）的点能够遍历到，这些点也能够遍历到，而入度为0的点显然能遍历到，故这些点也能被遍历到。证毕】
由于求反向图和拓扑排序都可以在O(M)时间内完成，整个去环过程的时间复杂度就是O(M)的。
下面附上NOI2009 pvz代码：（注意，本题的第9个点是一个超级大数据，最后建出来的网络的边数将会达到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;
}