程序竞赛中的网络流

/*==================================================*\ 
 | 二分图匹配（匈牙利算法DFS实现） 
 | INIT: g[][]邻接矩阵; 
 | CALL: res = MaxMatch(); 
 | 优点：实现简洁容易理解，适用于稠密图，DFS找增广路快。
 | 找一条增广路的复杂度为O（E），多找V条增广路，故时间复杂度为O（VE）
 \*==================================================*/  
const int MAXN = 1000;
int uN, vN;              // u, v数目，要初始化！！！ 
bool g[MAXN][MAXN];      // g[i][j] 表示xi与yj相连 
int xM[MAXN], yM[MAXN];  // 输出量 
bool chk[MAXN];          // 辅助量检查某轮y[v]是否被check  
bool SearchPath(int u) {
    int v;
    for (v = 0; v < vN; v++)
        if (g[u][v] && !chk[v]) {
            chk[v] = true;
            if (yM[v] == -1 || SearchPath(yM[v])) {
                yM[v] = u;
                xM[u] = v;
                return true;
            }
        }
    return false;
}

int MaxMatch() {
    int u, ret = 0;
    memset(xM, -1, sizeof(xM));
    memset(yM, -1, sizeof(yM));
    for (u = 0; u < uN; u++)
        if (xM[u] == -1) {
            memset(chk, false, sizeof(chk));
            if (SearchPath(u)) ret++;
        }
    return ret;
} 

/*==================================================*\ 
 | 二分图匹配（匈牙利算法BFS实现） 
 | INIT: g[][]邻接矩阵; 
 | CALL: res = MaxMatch();Nx, Ny初始化！！！ 
 | 优点：适用于稀疏二分图，边较少，增广路较短。 
 | 匈牙利算法的理论复杂度是O(VE) 
\*==================================================*/ 
const int MAXN = 1000;
int g[MAXN][MAXN], Mx[MAXN], My[MAXN], Nx, Ny;
int chk[MAXN], Q[MAXN], prev[MAXN];

int MaxMatch(void) {
    int res = 0;
    int qs, qe;
    memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
    memset(chk, -1, sizeof(chk));
    for (int i = 0; i < Nx; i++) {
        if (Mx[i] == -1) {
            qs = qe = 0;
            Q[qe++] = i;
            prev[i] = -1;
            bool flag = 0;
            while (qs < qe && !flag) {
                int u = Q[qs];
                for (int v = 0; v < Ny && !flag; v++)
                    if (g[u][v] && chk[v] != i) {
                        chk[v] = i;
                        Q[qe++] = My[v];
                        if (My[v] >= 0) prev[My[v]] = u;
                        else {
                            flag = 1;
                            int d = u, e = v;
                            while (d != -1) {
                                int t = Mx[d];
                                Mx[d] = e;
                                My[e] = d;
                                d = prev[d];
                                e = t;
                            }
                        }
                    }
                qs++;
            }
            if (Mx[i] != -1) res++;
        }
    }
    return res;
} 

/*==================================================*\ 
 | 二分图匹配（Hopcroft－Carp的算法） 
 | INIT: g[][]邻接矩阵; 
 | CALL: res = MaxMatch();   Nx, Ny要初始化！！！
 | 时间复杂度为O（V^0.5 E） 
\*==================================================*/ 
const int MAXN = 3001;
const int INF = 1 << 28;
int g[MAXN][MAXN], Mx[MAXN], My[MAXN], Nx, Ny;
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN];

bool searchP(void) {
    queue<int> Q;
    dis = INF;
    memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));
    for (int i = 0; i < Nx; i++)
        if (Mx[i] == -1) {
            Q.push(i);
            dx[i] = 0;
        }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        if (dx[u] > dis) break;
        for (int v = 0; v < Ny; v++)
            if (g[u][v] && dy[v] == -1) {
                dy[v] = dx[u] + 1;
                if (My[v] == -1) dis = dy[v];
                else {
                    dx[My[v]] = dy[v] + 1;
                    Q.push(My[v]);
                }
            }
    }
    return dis != INF;
}

bool DFS(int u) {
    for (int v = 0; v < Ny; v++)
        if (!vst[v] && g[u][v] && dy[v] == dx[u] + 1) {
            vst[v] = 1;
            if (My[v] != -1 && dy[v] == dis) continue;
            if (My[v] == -1 || DFS(My[v])) {
                My[v] = u;
                Mx[u] = v;
                return 1;
            }
        }
    return 0;
}

int MaxMatch(void) {
    int res = 0;
    memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
    while (searchP()) {
        memset(vst, 0, sizeof(vst));
        for (int i = 0; i < Nx; i++) if (Mx[i] == -1 && DFS(i)) res++;
    }
    return res;
} 

/*==================================================*\ 
 | 无向图最小割 O(N^3)  
 | INIT: 初始化邻接矩阵g[][]; 
 | CALL: res = mincut(n); 
 | 注: Stoer-Wagner Minimum Cut;
 | 找边的小集合，若其被删去则图变得不连通（我们把这种形式称为小 | 割问题） 
\*==================================================*/ 
#define typec int              // type of res
const typec inf = 0x3f3f3f3f;  // max of res const
typec maxw = 1000;             // maximum edge weight
typec g[V][V], w[V];
int a[V], v[V], na[V];

typec mincut(int n) {
    int i, j, pv, zj;
    typec best = maxw * n * n;
    for (i = 0; i < n; i++)
        v[i] = i;  // vertex: 0 ~ n-1
    while (n > 1) {
        for (a[v[0]] = 1, i = 1; i < n; i++) {
            a[v[i]] = 0;
            na[i - 1] = i;
            w[i] = g[v[0]][v[i]];
        }
        for (pv = v[0], i = 1; i < n; i++) {
            for (zj = -1, j = 1; j < n; j++)
                if (!a[v[j]] && (zj < 0 || w[j] > w[zj]))zj = j;
            a[v[zj]] = 1;
            if (i == n - 1) {
                if (best > w[zj]) best = w[zj];
                for (i = 0; i < n; i++) g[v[i]][pv] = g[pv][v[i]] += g[v[zj]][v[i]];
                v[zj] = v[--n];
                break;
            }
            pv = v[zj];
            for (j = 1; j < n; j++) if (!a[v[j]]) w[j] += g[v[zj]][v[j]];
        }
    }
    return best;
}

/*==================================================*\ 
 | Dinic最大流 O(V^2 * E) 
 | INIT: ne=2; head[]置为0; addedge()加入所有弧; 
 | CALL: flow(n, s, t); 
\*==================================================*/ 
#define typec int                   // type of cost 
const typec inf = 0x3f3f3f3f;       // max of cost 
struct edge {
    int x, y, nxt;
    typec c;
} bf[E];
int ne, head[N], cur[N], ps[N], dep[N];

void addedge(int x, int y,
             typec c) { // add an arc(x -> y, c); vertex: 0 ~ n-1;  
    bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;
    bf[ne].nxt = head[x];
    head[x] = ne++;
    bf[ne].x = y; bf[ne].y = x; bf[ne].c = 0;
    bf[ne].nxt = head[y];
    head[y] = ne++;
}

typec flow(int n, int s, int t) {
    typec tr, res = 0;
    int i, j, k, f, r, top;
    while (1) {
        memset(dep, -1, n * sizeof(int));
        for (f = dep[ps[0] = s] = 0, r = 1; f != r;)
            for (i = ps[f++], j = head[i]; j; j = bf[j].nxt) {
                if (bf[j].c && -1 == dep[k = bf[j].y]) {
                    dep[k] = dep[i] + 1;
                    ps[r++] = k;
                    if (k == t) {
                        f = r;
                        break;
                    }
                }
            }
        if (-1 == dep[t]) break;
        memcpy(cur, head, n * sizeof(int));
        for (i = s, top = 0;;) {
            if (i == t) {
                for (k = 0, tr = inf; k < top; ++k)
                    if (bf[ps[k]].c < tr)
                        tr = bf[ps[f = k]].c;
                for (k = 0; k < top; ++k) 
                    bf[ps[k]].c -= tr, bf[ps[k] ^ 1].c += tr;
                res += tr;
                i = bf[ps[top = f]].x;
            }
            for (j = cur[i]; cur[i]; j = cur[i] = bf[cur[i]].nxt) 
                if (bf[j].c && dep[i] + 1 == dep[bf[j].y]) 
                    break;
            if (cur[i]) {
                ps[top++] = cur[i];
                i = bf[cur[i]].y;
            } else {
                if (0 == top) break;
                dep[i] = -1;
                i = bf[ps[--top]].x;
            }
        }
    }
    return res;
}