Index: lib/graph/maxFlow.cpp
==================================================================
--- lib/graph/maxFlow.cpp
+++ lib/graph/maxFlow.cpp
@@ -4,11 +4,11 @@
 //   O(V E)
 //
 // G : bidirectional (G[i].has(j) <==> G[j].has(i))
 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0
 //
-// Verified by
+// Old versoin Verified by
 //   - SRM 399 Div1 LV3
 //   - PKU 1459
 //   - CodeCraft 09 CUTS
 //   - SRM 465 Div1 LV2
 //   - SRM 543 Div1 LV3
@@ -26,25 +26,42 @@
 	}
 	const T& id2v(int i) const { return id2v_[i]; }
 	int size() const { return id2v_.size(); }
 };
 
-template<typename Vert, typename Flow, int NV=2048>
+template<typename Vert, typename Flow, int NV=50*50*8+2>
 class MaxFlow
 {
+	typedef int Edge;
+
+	vector<int>  G[NV];
+	vector<Flow> F;
+
 	IdGen<Vert> idgen;
-	vector<int> G[NV];
-	Flow F[NV][NV];
+	map<pair<int,int>, Edge> edge_id;
+	vector<int>  Edge_to;
+	vector<Edge> Edge_rev;
 
 public:
-	void addEdge( Vert s_, Vert t_, Flow f )
+	void add( 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;
+		if(!edge_id.count(make_pair(s,t))) {
+			const int e = int(edge_id.size());
+			edge_id[make_pair(s,t)] = e;
+			edge_id[make_pair(t,s)] = e+1;
+			G[s].push_back(e);
+			G[t].push_back(e+1);
+			F.push_back(0);
+			F.push_back(0);
+			Edge_rev.push_back(e+1);
+			Edge_rev.push_back(e);
+			Edge_to.push_back(t);
+			Edge_to.push_back(s);
+		}
+		const Edge e = edge_id[make_pair(s,t)];
+		F[e] = min(F[e]+f, INF);
 	}
 
 	Flow calc( Vert s_, Vert t_ )
 	{
 		const int S = idgen.v2id(s_), D = idgen.v2id(t_);
@@ -53,14 +70,17 @@
 			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]);
+					const vector<Edge>& ne = G[Q[i]];
+					for(size_t j=0; j!=ne.size(); ++j) {
+						Edge e = ne[j];
+						int  t = Edge_to[e];
+						if( F[e] && !LV[t] && t!=S )
+							LV[t]=lv, Q2.push_back(t);
+					}
 				}
 				Q.swap(Q2);
 			}
 
 			// Destination is now unreachable. Done.
@@ -67,29 +87,30 @@
 			if( !LV[D] )
 				return total;
 
 			// Iterating DFS.
 			bool blocked[NV] = {};
-			total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
+			total += dinic_dfs( S, D, LV, INF, 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]);
+			Edge e = G[v][i];
+			int  u = Edge_to[e];
+			if( LV[v]+1==LV[u] && F[e] ) {
+				Flow f = min(flow_in-flow_out, F[e]);
 				if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
-					F[v][u]  -= f;
-					F[u][v]  += f;
+					F[e]           -= f;
+					F[Edge_rev[e]] += f;
 					flow_out += f;
 					if( flow_in == flow_out ) return flow_out;
 				}
 			}
 		}
 		blocked[v] = (flow_out==0);
 		return flow_out;
 	}
 };