Maximum Flow and BPM Problems from SPOJ and HDU

Here is a short list of network flow and bpm problems that I managed to solve from SPOJ and HDU. This is not much and there are other sources of these kinds of problems, but I think these are some good starting points. Also I did not classify them on the types of flow or bpm, that would be up to the reader.

Maximum Flow and Bipartite Matching problems from SPOJ

ANGELS	BABY	DIVREL	FASTFLOW	MATCHING
MSE06I	MTOTALF	MUDDY	PCPC12H	PROFIT
PT07X	QUEST4	SCITIES	STEAD	TAXI

Maximum Flow and Bipartite Matching problems from HDU

1532	1533	1853	2448	2686
2732	2833	3081	3277	3315
3376	3395	3416	3419	3435
3468	3472	3488	3491	3572
3667	3987	3998	4183	4309

Note: UVa has a lot of flow and bpm problems, please visit uHunt for guidelines.

Note: It is very possible that there are many other problems from these online judges which can be solved by flow or bpm algorithms. And, some problems here could be mistakenly added as flow or bpm category due to copy paste errors. Please feel free to leave a note on the comment section, add more links if you like to. Happy coding \m/

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.

Maximum Matching (Hopcroft)

Hopcroft-Karp is one of the fastest algorithm that finds the maximum cardinality matching on a bipartite graph. It has the best known worst case time complexity. More details can be found here [courtesy of Wikipedia].

C++ Source Code:

#define MAX 100001
#define NIL 0
#define INF (1<<28)

vector< int > G[MAX];
int n, m, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]

bool bfs() {
    int i, u, v, len;
    queue< int > Q;
    for(i=1; i<=n; i++) {
        if(match[i]==NIL) {
            dist[i] = 0;
            Q.push(i);
        }
        else dist[i] = INF;
    }
    dist[NIL] = INF;
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        if(u!=NIL) {
            len = G[u].size();
            for(i=0; i<len; i++) {
                v = G[u][i];
                if(dist[match[v]]==INF) {
                    dist[match[v]] = dist[u] + 1;
                    Q.push(match[v]);
                }
            }
        }
    }
    return (dist[NIL]!=INF);
}

bool dfs(int u) {
    int i, v, len;
    if(u!=NIL) {
        len = G[u].size();
        for(i=0; i<len; i++) {
            v = G[u][i];
            if(dist[match[v]]==dist[u]+1) {
                if(dfs(match[v])) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF;
        return false;
    }
    return true;
}

int hopcroft_karp() {
    int matching = 0, i;
    // match[] is assumed NIL for all vertex in G
    while(bfs())
        for(i=1; i<=n; i++)
            if(match[i]==NIL && dfs(i))
                matching++;
    return matching;
}

The implementation is quite straight forward as the algorithm on Wikipedia page. I am looking for some optimizations.