4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // Bipertite max-matching (by duality, min-vert-cover)
4fd800b3a8 2011-02-23        kinaba: //   O(V E)
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   SRM 397 Div1 Lv3
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: typedef int           vert;
4fd800b3a8 2011-02-23        kinaba: typedef vert          edge;
4fd800b3a8 2011-02-23        kinaba: typedef vector<edge>  edges;
4fd800b3a8 2011-02-23        kinaba: typedef vector<edges> graph;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	for(int i=0; i<G[v].size(); ++i) {
4fd800b3a8 2011-02-23        kinaba: 		vert u = G[v][i];
4fd800b3a8 2011-02-23        kinaba: 		if( visited[u] ) continue;
4fd800b3a8 2011-02-23        kinaba: 		visited[u] = true;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
4fd800b3a8 2011-02-23        kinaba: 			{ matchTo[v]=u, matchTo[u]=v; return true; }
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return false;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int NV>
4fd800b3a8 2011-02-23        kinaba: int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
4fd800b3a8 2011-02-23        kinaba:     // only left->right edges are used during computation
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	vector<vert> matchTo(G.size(), -1);
4fd800b3a8 2011-02-23        kinaba: 	int ans = 0;
4fd800b3a8 2011-02-23        kinaba: 	for(vert v=0; v<L; ++v) {
4fd800b3a8 2011-02-23        kinaba: 		bool visited[NV] = {};
4fd800b3a8 2011-02-23        kinaba: 		if( augment(G, v, matchTo, visited) )
4fd800b3a8 2011-02-23        kinaba: 			++ans;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return ans;
4fd800b3a8 2011-02-23        kinaba: }