MaxFlow :: Dinitz Algorithm

Here is a nice implementation of Dinitz blocking flow algorithm in C++ (with special thanks to Fahim vai). Works in undirected large graph containing multiple edges and self loops as well. No STL used. This implementation is pretty fast.

Here, input is, number of nodes 2≤n≤5000, number of input edges 0≤e≤30000, then e undirected edges in the form (u, v, cap) (1≤u,v≤n and 1≤cap≤10^9). Source and Sink are assumed 1 and n accordingly, can be changed in the init() function call.

#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define i64 long long

const int INF = 0x7fffffff;
const int MAXN = 5005, MAXE = 60006;

int src, snk, nNode, nEdge;
int Q[MAXN], fin[MAXN], pro[MAXN], dist[MAXN];
int flow[MAXE], cap[MAXE], next[MAXE], to[MAXE];

inline void init(int _src, int _snk, int _n) {
    src = _src, snk = _snk, nNode = _n, nEdge = 0;
    SET(fin);
}

inline void add(int u, int v, int c) {
    to[nEdge] = v, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[u], fin[u] = nEdge++;
    to[nEdge] = u, cap[nEdge] = c, flow[nEdge] = 0, next[nEdge] = fin[v], fin[v] = nEdge++;
}

bool bfs() {
    int st, en, i, u, v;
    SET(dist);
    dist[src] = st = en = 0;
    Q[en++] = src;
    while(st < en) {
        u = Q[st++];
        for(i=fin[u]; i>=0; i=next[i]) {
            v = to[i];
            if(flow[i] < cap[i] && dist[v]==-1) {
                dist[v] = dist[u]+1;
                Q[en++] = v;
            }
        }
    }
    return dist[snk]!=-1;
}

int dfs(int u, int fl) {
    if(u==snk) return fl;
    for(int &e=pro[u], v, df; e>=0; e=next[e]) {
        v = to[e];
        if(flow[e] < cap[e] && dist[v]==dist[u]+1) {
            df = dfs(v, min(cap[e]-flow[e], fl));
            if(df>0) {
                flow[e] += df;
                flow[e^1] -= df;
                return df;
            }
        }
    }
    return 0;
}

i64 dinitz() {
    i64 ret = 0;
    int df;
    while(bfs()) {
        for(int i=1; i<=nNode; i++) pro[i] = fin[i];
        while(true) {
            df = dfs(src, INF);
            if(df) ret += (i64)df;
            else break;
        }
    }
    return ret;
}

int main() {
    int n, e, u, v, c, i;
    scanf("%d%d", &n, &e);
    init(1, n, n);
    for(i=0; i<e; i++) {
        scanf("%d%d%d", &u, &v, &c);
        if(u!=v) add(u, v, c);
    }
    printf("%lld\n", dinitz());
    return 0;
}

Using adjacency matrix and/or STL makes it 10 to 4 times slower.

C++ :: Get Variable's Name

How to print a variables name instead of its value? (not just by giving the name yourself)

This can be easily done with a #define pre-processor directive. As #define treats the preceding expression as cstring, it is possible to get the variables name as a string. Look below:

#include <stdio.h>

#define getVarName(varName,holder) sprintf(holder, "%s", #varName)

int main() {
    int var = 100; // just any type of identifier
    char name[100]; // it will get the variables name
    getVarName(var, name);
    puts(name);
    return 0;
}

It will print "var" instead of "100" or something other. I saw it years ago somewhere I can't remember now. Today, it suddenly struck me and I think it might be useful who knows when...

Maximum Matching (DFS)

Maximum bipartite matching in a bipartite graph

Although Hopcroft Karp is faster and smarter, this one is pretty simple to code specially in contest time and when the graph is relatively smaller. It uses a DFS subroutine to cut and establish matching and thus produces a maximum matching. This version of BPM takes the adjacency list of left side of the bipartite graph and updates the Left[] and Right[] arrays with their respective matches.

Here, in the DFS subroutine, there are two for loops, where, the first one checks for yet unestablished connections, and the second one is the recursive DFS step. These two steps could be written in a single loop and the condition modified as "( Right[v]==-1 || dfs(Right[v]) )", actually separating them increases performance by some factors, because, first time it checks all the unmatched nodes before going into DFS.

A sample C++ implementation:

#define SET(x) memset(x, -1, sizeof(x))
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100

vector < int > edges[MAX];
bool visited[MAX];
int Left[MAX], Right[MAX];

bool dfs(int u) {
    if(visited[u]) return false;
    visited[u] = true;
    int len = edges[u].size(), i, v;
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(Right[v]==-1) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(dfs(Right[v])) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    return false;
}

int match() {
    SET(Left);
    SET(Right);
    int i, ret = 0;
    bool done;
    do {
        done = true;
        CLR(visited);
        for(i=0; i<MAX; i++) {
            if(Left[i]==-1 && dfs(i)) {
                done = false;
            }
        }
    } while(!done);
    for(i=0; i<MAX; i++) ret += (Left[i]!=-1);
    return ret;
}

Notes: Here, edges[MAX] is the left side adjacency list, implemented with vector, Left[MAX] and Right[MAX] holds the matching and the procedure match() returns maximum matching. Pretty straight forward.