2013-team5/network-flow

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/*
    dinic 
    O(n^2*m)
    first initial S & T
    By Kotomi
*/

#include <cstring>
#include <queue>

using namespace std;

const int maxN = 2010;
const int maxM = 1000000;
const int INF = 1 << 30;

struct graph
{
    int v, next, op, c;
}edge[maxM];

int lv[maxN], vect[maxN];
int S, T, tot;

void add(int u, int v, int c)
{
    edge[++tot].v = v;
    edge[tot].c = c;
    edge[tot].next = vect[u];
    vect[u] = tot;
    edge[tot].op = tot + 1;

    edge[++tot].v = u;
    edge[tot].c = 0;
    edge[tot].next = vect[v];
    vect[v] = tot;
    edge[tot].op = tot - 1;
}

bool build()
{
    memset(lv, 0, sizeof(lv));
    queue<int> Q;
    Q.push(S);
    lv[S] = 1;
    while (!Q.empty()){
            int u = Q.front();
            Q.pop();
            for (int it = vect[u]; it; it = edge[it].next){
                    int v = edge[it].v; 
                    int c = edge[it].c;
                    if (c > 0 && !lv[v]){
                            lv[v] = lv[u] + 1;
                            Q.push(v);
                            if (v == T) return true;
                    }
            }
    }
    return false;   
}

int dfs(int u, int flow)
{
    if (u == T || !flow) return flow;
    int tp, now = 0;
    for (int it = vect[u]; it; it = edge[it].next){
            int v = edge[it].v;
            int c = edge[it].c;
            int op = edge[it].op;
            if (c > 0 && lv[u] + 1 == lv[v]){
                tp = dfs(v, min(flow, c));
                now = now + tp;
                flow = flow - tp;     
                edge[it].c -= tp;
                edge[op].c += tp;
            }    
    }
    if (!now) lv[u] = 0; 
    return now;
}

int dinic()
{
    int ans = 0;
    while (build()) ans += dfs(S, INF);
    return ans;
}

int init(int s, int t)
{
    S = s, T = t, tot = 0;
    memset(vect, 0, sizeof(vect));
}

}}}

/*
    dinic 
    O(n^2*m)
    first initial S & T
    By Kotomi
*/
#include <cstring>
#include <queue>
using namespace std;
const int maxN = 2010;
const int maxM = 1000000;
const int INF = 1 << 30;
struct graph
{
    int v, next, op, c;
}edge[maxM];
int lv[maxN], vect[maxN];
int S, T, tot;
void add(int u, int v, int c)
{
    edge[++tot].v = v;
    edge[tot].c = c;
    edge[tot].next = vect[u];
    vect[u] = tot;
    edge[tot].op = tot + 1;
    edge[++tot].v = u;
    edge[tot].c = 0;
    edge[tot].next = vect[v];
    vect[v] = tot;
    edge[tot].op = tot - 1;
}
bool build()
{
    memset(lv, 0, sizeof(lv));
    queue<int> Q;
    Q.push(S);
    lv[S] = 1;
    while (!Q.empty()){
            int u = Q.front();
            Q.pop();
            for (int it = vect[u]; it; it = edge[it].next){
                    int v = edge[it].v; 
                    int c = edge[it].c;
                    if (c > 0 && !lv[v]){
                            lv[v] = lv[u] + 1;
                            Q.push(v);
                            if (v == T) return true;
                    }
            }
    }
    return false;   
}
int dfs(int u, int flow)
{
    if (u == T || !flow) return flow;
    int tp, now = 0;
    for (int it = vect[u]; it; it = edge[it].next){
            int v = edge[it].v;
            int c = edge[it].c;
            int op = edge[it].op;
            if (c > 0 && lv[u] + 1 == lv[v]){
                tp = dfs(v, min(flow, c));
                now = now + tp;
                flow = flow - tp;     
                edge[it].c -= tp;
                edge[op].c += tp;
            }    
    }
    if (!now) lv[u] = 0; 
    return now;
}
int dinic()
{
    int ans = 0;
    while (build()) ans += dfs(S, INF);
    return ans;
}
int init(int s, int t)
{
    S = s, T = t, tot = 0;
    memset(vect, 0, sizeof(vect));
}