4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: static const int NV = 512;
4fd800b3a8 2011-02-23        kinaba: typedef int           flow;
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: typedef flow          flow_graph[NV][NV];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: flow dinic_dfs( graph& G, flow_graph F, vert v, vert D,
4fd800b3a8 2011-02-23        kinaba:                 int LV[], flow flow_in, int blocked[] )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	flow flow_out = 0;
4fd800b3a8 2011-02-23        kinaba: 	for(int i=0; i!=G[v].size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int u = G[v][i];
4fd800b3a8 2011-02-23        kinaba: 		if( LV[v]+1==LV[u] && F[v][u] )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			flow f = min(flow_in-flow_out, F[v][u]);
4fd800b3a8 2011-02-23        kinaba: 			if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				F[v][u]  -= f;
4fd800b3a8 2011-02-23        kinaba: 				F[u][v]  += f;
4fd800b3a8 2011-02-23        kinaba: 				flow_out += f;
4fd800b3a8 2011-02-23        kinaba: 				if( flow_in == flow_out ) return flow_out;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	blocked[v] = (flow_out==0);
4fd800b3a8 2011-02-23        kinaba: 	return flow_out;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: flow dinic( graph& G, flow_graph F, vert S, vert D )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	for( flow total=0 ;; ) {
4fd800b3a8 2011-02-23        kinaba: 		int LV[NV] = {0};
4fd800b3a8 2011-02-23        kinaba: 		vector<int> Q(1, S);
4fd800b3a8 2011-02-23        kinaba: 		for(int lv=1; !Q.empty(); ++lv)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			vector<int> Q2;
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i!=Q.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				edges& ne = G[Q[i]];
4fd800b3a8 2011-02-23        kinaba: 				for(int j=0; j!=ne.size(); ++j)
4fd800b3a8 2011-02-23        kinaba: 					if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
4fd800b3a8 2011-02-23        kinaba: 						LV[ne[j]]=lv, Q2.push_back(ne[j]);
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			Q.swap(Q2);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( !LV[D] )
4fd800b3a8 2011-02-23        kinaba: 			return total;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int blocked[NV] = {};
4fd800b3a8 2011-02-23        kinaba: 		total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked );
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct DancingParty
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	int maxDances(vector<string> likes, int k)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int n = likes.size();
4fd800b3a8 2011-02-23        kinaba: 		#define SRC 0
4fd800b3a8 2011-02-23        kinaba: 		#define DST 1
4fd800b3a8 2011-02-23        kinaba: 		#define L(i)  2+n*0+i
4fd800b3a8 2011-02-23        kinaba: 		#define R(i)  2+n*1+i
4fd800b3a8 2011-02-23        kinaba: 		#define YL(i) 2+n*2+i
4fd800b3a8 2011-02-23        kinaba: 		#define NL(i) 2+n*3+i
4fd800b3a8 2011-02-23        kinaba: 		#define YR(i) 2+n*4+i
4fd800b3a8 2011-02-23        kinaba: 		#define NR(i) 2+n*5+i
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		graph G(2+n*6);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// Graph
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<n; ++i) {
4fd800b3a8 2011-02-23        kinaba: 			G[SRC ].push_back(L(i));  G[L(i) ].push_back(SRC);
4fd800b3a8 2011-02-23        kinaba: 			G[L(i)].push_back(YL(i)); G[YL(i)].push_back(L(i));
4fd800b3a8 2011-02-23        kinaba: 			G[L(i)].push_back(NL(i)); G[NL(i)].push_back(L(i));
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			G[DST ].push_back(R(i));  G[R(i) ].push_back(DST);
4fd800b3a8 2011-02-23        kinaba: 			G[R(i)].push_back(YR(i)); G[YR(i)].push_back(R(i));
4fd800b3a8 2011-02-23        kinaba: 			G[R(i)].push_back(NR(i)); G[NR(i)].push_back(R(i));
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			for(int j=0; j<n; ++j)
4fd800b3a8 2011-02-23        kinaba: 				if( likes[i][j] == 'Y' )
4fd800b3a8 2011-02-23        kinaba: 					G[YL(i)].push_back(YR(j)), G[YR(j)].push_back(YL(i));
4fd800b3a8 2011-02-23        kinaba: 				else
4fd800b3a8 2011-02-23        kinaba: 					G[NL(i)].push_back(NR(j)), G[NR(j)].push_back(NL(i));
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(int M=1; M<=n; ++M) {
4fd800b3a8 2011-02-23        kinaba: 			// Flow
4fd800b3a8 2011-02-23        kinaba: 			flow_graph F = {};
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<n; ++i) {
4fd800b3a8 2011-02-23        kinaba: 				F[SRC][L(i)] = M;
4fd800b3a8 2011-02-23        kinaba: 				F[L(i)][YL(i)] = M;
4fd800b3a8 2011-02-23        kinaba: 				F[L(i)][NL(i)] = k;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				F[R(i)][DST] = M;
4fd800b3a8 2011-02-23        kinaba: 				F[YR(i)][R(i)] = M;
4fd800b3a8 2011-02-23        kinaba: 				F[NR(i)][R(i)] = k;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				for(int j=0; j<n; ++j)
4fd800b3a8 2011-02-23        kinaba: 					if( likes[i][j] == 'Y' )
4fd800b3a8 2011-02-23        kinaba: 						F[YL(i)][YR(j)] = 1;
4fd800b3a8 2011-02-23        kinaba: 					else
4fd800b3a8 2011-02-23        kinaba: 						F[NL(i)][NR(j)] = 1;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			// Maxflow
4fd800b3a8 2011-02-23        kinaba: 			if( dinic(G, F, SRC, DST) < M*n )
4fd800b3a8 2011-02-23        kinaba: 				return M-1;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return n;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };