2018-team4-modules-最大流/最小割

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct Edge{int b,v,n;}e[M];
void add_Edge(int a,int b,int v) { e[++cnt] = (Edge){b,v,h[a]}, h[a] = cnt; }
void add(int a,int b,int v) {add_Edge(a,b,v),add_Edge(b,a,0);}

bool BFS() {
    bool flag = 0;
    for (int i=1;i<=tot;i++) p[i] = 0;
    for (int i=1;i<=tot;i++) cur[i] = h[i];
    queue<int> q;
    p[S] = 1;
    q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == T) flag = 1;
        for (int i=h[u];i;i=e[i].n) {
            int v = e[i].b, cp = e[i].v;
            if (!p[v] && cp > 0)
                p[v] = p[u] + 1, q.push(v);
        }
    }
    return flag;
}

int DFS(int u,int flow) {
    if (u == T) return flow;
    int f = flow, g = 0;
    for (int i=cur[u];i;i=e[i].n) {
        cur[u] = i;
        int v = e[i].b, cp = e[i].v, tmp = 0;
        if (p[v] == p[u]+1 && cp>0 && (tmp=DFS(v,min(f,cp))) >0) {
            e[i].v -= tmp;
            e[i^1].v += tmp;
            f -= tmp;
            g += tmp;
        }
    }
    return g;
}
}}}

struct Edge{int b,v,n;}e[M];
void add_Edge(int a,int b,int v) { e[++cnt] = (Edge){b,v,h[a]}, h[a] = cnt; }
void add(int a,int b,int v) {add_Edge(a,b,v),add_Edge(b,a,0);}
bool BFS() {
    bool flag = 0;
    for (int i=1;i<=tot;i++) p[i] = 0;
    for (int i=1;i<=tot;i++) cur[i] = h[i];
    queue<int> q;
    p[S] = 1;
    q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == T) flag = 1;
        for (int i=h[u];i;i=e[i].n) {
            int v = e[i].b, cp = e[i].v;
            if (!p[v] && cp > 0)
                p[v] = p[u] + 1, q.push(v);
        }
    }
    return flag;
}
int DFS(int u,int flow) {
    if (u == T) return flow;
    int f = flow, g = 0;
    for (int i=cur[u];i;i=e[i].n) {
        cur[u] = i;
        int v = e[i].b, cp = e[i].v, tmp = 0;
        if (p[v] == p[u]+1 && cp>0 && (tmp=DFS(v,min(f,cp))) >0) {
            e[i].v -= tmp;
            e[i^1].v += tmp;
            f -= tmp;
            g += tmp;
        }
    }
    return g;
}