Index: CheckList.pptx
==================================================================
--- CheckList.pptx
+++ CheckList.pptx
cannot compute difference between binary files

Index: lib/graph/maxFlow.cpp
==================================================================
--- lib/graph/maxFlow.cpp
+++ lib/graph/maxFlow.cpp
@@ -11,56 +11,84 @@
 //   - PKU 1459
 //   - CodeCraft 09 CUTS
 //   - SRM 465 Div1 LV2
 //-------------------------------------------------------------
 
-static const int NV = 512;
-typedef int           flow;
-typedef int           vert;
-typedef vert          edge;
-typedef vector<edge>  edges;
-typedef vector<edges> graph;
-typedef flow          flow_graph[NV][NV];
-
-flow dinic_dfs( graph& G, flow_graph F, vert v, vert D,
-                int LV[], flow flow_in, int blocked[] )
+template<typename T>
+class IdGen
 {
-	flow flow_out = 0;
-	for(int i=0; i!=G[v].size(); ++i) {
-		int u = G[v][i];
-		if( LV[v]+1==LV[u] && F[v][u] ) {
-			flow f = min(flow_in-flow_out, F[v][u]);
-			if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) ) {
-				F[v][u]  -= f;
-				F[u][v]  += f;
-				flow_out += f;
-				if( flow_in == flow_out ) return flow_out;
-			}
-		}
+	map<T, int> v2id_;
+	vector<T>   id2v_;
+public:
+	int v2id(const T& v) {
+		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
+		return v2id_[v];
 	}
-	blocked[v] = (flow_out==0);
-	return flow_out;
-}
+	const T& id2v(int i) const { return id2v_[i]; }
+	int size() const { return id2v_.size(); }
+};
 
-flow maxFlow( graph& G, flow_graph F, vert S, vert D )
+template<typename Vert, typename Flow, int NV=512>
+class MaxFlow
 {
-	for( flow total=0 ;; ) {
-		int LV[NV] = {0};
-		vector<int> Q(1, S);
-		for(int lv=1; !Q.empty(); ++lv) {
-			vector<int> Q2;
-			for(int i=0; i!=Q.size(); ++i) {
-				edges& ne = G[Q[i]];
-				for(int j=0; j!=ne.size(); ++j)
-					if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
-						LV[ne[j]]=lv, Q2.push_back(ne[j]);
+	IdGen<Vert> idgen;
+	vector<int> G[NV];
+	Flow F[NV][NV];
+
+public:
+	void addEdge( Vert s_, Vert t_, Flow f )
+	{
+		const int s = idgen.v2id(s_), t = idgen.v2id(t_);
+		G[s].push_back(t);
+		G[t].push_back(s);
+		F[s][t] = f;
+		F[t][s] = 0;
+	}
+
+	Flow calc( Vert s_, Vert t_ )
+	{
+		const int S = idgen.v2id(s_), D = idgen.v2id(t_);
+		for( Flow total=0 ;; ) {
+			// Do BFS and compute the level for each node.
+			int LV[NV] = {0};
+			vector<int> Q(1, S);
+			for(int lv=1; !Q.empty(); ++lv) {
+				vector<int> Q2;
+				for(size_t i=0; i!=Q.size(); ++i) {
+					const vector<int>& ne = G[Q[i]];
+					for(size_t j=0; j!=ne.size(); ++j)
+						if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
+							LV[ne[j]]=lv, Q2.push_back(ne[j]);
+				}
+				Q.swap(Q2);
 			}
-			Q.swap(Q2);
-		}
+
+			// Destination is now unreachable. Done.
+			if( !LV[D] )
+				return total;
 
-		if( !LV[D] )
-			return total;
+			// Iterating DFS.
+			bool blocked[NV] = {};
+			total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
+		}
+	}
 
-		int blocked[NV] = {};
-		total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked );
+private:
+	Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
+	{
+		Flow flow_out = 0;
+		for(size_t i=0; i!=G[v].size(); ++i) {
+			int u = G[v][i];
+			if( LV[v]+1==LV[u] && F[v][u] ) {
+				Flow f = min(flow_in-flow_out, F[v][u]);
+				if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
+					F[v][u]  -= f;
+					F[u][v]  += f;
+					flow_out += f;
+					if( flow_in == flow_out ) return flow_out;
+				}
+			}
+		}
+		blocked[v] = (flow_out==0);
+		return flow_out;
 	}
-}
+};