1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 1 4 #include <vector> 2 5 #include <string> 3 -#include <iostream> 4 -#include <cstring> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <memory> 12 +#include <functional> 13 +#include <complex> 14 +#include <queue> 15 +#include <stack> 16 +#include <cmath> 17 +#include <cassert> 5 18 using namespace std; 19 +typedef long long LL; 20 +typedef long double LD; 21 +typedef complex<LD> CMP; 6 22 7 - 8 - 9 - 10 -static const int NV = 512; 11 -typedef int flow; 12 -typedef int vert; 13 -typedef vert edge; 14 -typedef vector<edge> edges; 15 -typedef vector<edges> graph; 16 -typedef flow flow_graph[NV][NV]; 17 - 18 -flow dinic_dfs( graph& G, flow_graph F, vert v, vert D, 19 - int LV[], flow flow_in, int blocked[] ) 23 +template<typename T> 24 +class IdGen 20 25 { 21 - flow flow_out = 0; 22 - for(int i=0; i!=G[v].size(); ++i) 23 - { 24 - int u = G[v][i]; 25 - if( LV[v]+1==LV[u] && F[v][u] ) 26 - { 27 - flow f = min(flow_in-flow_out, F[v][u]); 28 - if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) ) 29 - { 30 - F[v][u] -= f; 31 - F[u][v] += f; 32 - flow_out += f; 33 - if( flow_in == flow_out ) return flow_out; 34 - } 35 - } 26 + map<T, int> v2id_; 27 + vector<T> id2v_; 28 +public: 29 + int v2id(const T& v) { 30 + if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 31 + return v2id_[v]; 36 32 } 37 - blocked[v] = (flow_out==0); 38 - return flow_out; 39 -} 33 + const T& id2v(int i) const { return id2v_[i]; } 34 + int size() const { return id2v_.size(); } 35 +}; 40 36 41 -flow dinic( graph& G, flow_graph F, vert S, vert D ) 37 +template<typename Vert, typename Flow, int NV=512> 38 +class MaxFlow 42 39 { 43 - for( flow total=0 ;; ) { 44 - int LV[NV] = {0}; 45 - vector<int> Q(1, S); 46 - for(int lv=1; !Q.empty(); ++lv) 47 - { 48 - vector<int> Q2; 49 - for(int i=0; i!=Q.size(); ++i) 50 - { 51 - edges& ne = G[Q[i]]; 52 - for(int j=0; j!=ne.size(); ++j) 53 - if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S ) 54 - LV[ne[j]]=lv, Q2.push_back(ne[j]); 55 - } 56 - Q.swap(Q2); 57 - } 40 + IdGen<Vert> idgen; 41 + vector<int> G[NV]; 42 + Flow F[NV][NV]; 58 43 59 - if( !LV[D] ) 60 - return total; 61 - 62 - int blocked[NV] = {}; 63 - total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked ); 44 +public: 45 + void addEdge( Vert s_, Vert t_, Flow f ) 46 + { 47 + const int s = idgen.v2id(s_), t = idgen.v2id(t_); 48 + G[s].push_back(t); 49 + G[t].push_back(s); 50 + F[s][t] = f; 51 + F[t][s] = 0; 64 52 } 65 -} 66 53 67 - 68 - 69 -struct DancingParty 70 -{ 71 - int maxDances(vector<string> likes, int k) 54 + Flow calc( Vert s_, Vert t_ ) 72 55 { 73 - int n = likes.size(); 74 - #define SRC 0 75 - #define DST 1 76 - #define L(i) 2+n*0+i 77 - #define R(i) 2+n*1+i 78 - #define YL(i) 2+n*2+i 79 - #define NL(i) 2+n*3+i 80 - #define YR(i) 2+n*4+i 81 - #define NR(i) 2+n*5+i 56 + const int S = idgen.v2id(s_), D = idgen.v2id(t_); 57 + for( Flow total=0 ;; ) { 58 + // Do BFS and compute the level for each node. 59 + int LV[NV] = {0}; 60 + vector<int> Q(1, S); 61 + for(int lv=1; !Q.empty(); ++lv) { 62 + vector<int> Q2; 63 + for(size_t i=0; i!=Q.size(); ++i) { 64 + const vector<int>& ne = G[Q[i]]; 65 + for(size_t j=0; j!=ne.size(); ++j) 66 + if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S ) 67 + LV[ne[j]]=lv, Q2.push_back(ne[j]); 68 + } 69 + Q.swap(Q2); 70 + } 71 + 72 + // Destination is now unreachable. Done. 73 + if( !LV[D] ) 74 + return total; 75 + 76 + // Iterating DFS. 77 + bool blocked[NV] = {}; 78 + total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); 79 + } 80 + } 82 81 83 - graph G(2+n*6); 84 - 85 - // Graph 86 - for(int i=0; i<n; ++i) { 87 - G[SRC ].push_back(L(i)); G[L(i) ].push_back(SRC); 88 - G[L(i)].push_back(YL(i)); G[YL(i)].push_back(L(i)); 89 - G[L(i)].push_back(NL(i)); G[NL(i)].push_back(L(i)); 90 - 91 - G[DST ].push_back(R(i)); G[R(i) ].push_back(DST); 92 - G[R(i)].push_back(YR(i)); G[YR(i)].push_back(R(i)); 93 - G[R(i)].push_back(NR(i)); G[NR(i)].push_back(R(i)); 94 - 95 - for(int j=0; j<n; ++j) 96 - if( likes[i][j] == 'Y' ) 97 - G[YL(i)].push_back(YR(j)), G[YR(j)].push_back(YL(i)); 98 - else 99 - G[NL(i)].push_back(NR(j)), G[NR(j)].push_back(NL(i)); 82 +private: 83 + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 84 + { 85 + Flow flow_out = 0; 86 + for(size_t i=0; i!=G[v].size(); ++i) { 87 + int u = G[v][i]; 88 + if( LV[v]+1==LV[u] && F[v][u] ) { 89 + Flow f = min(flow_in-flow_out, F[v][u]); 90 + if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) { 91 + F[v][u] -= f; 92 + F[u][v] += f; 93 + flow_out += f; 94 + if( flow_in == flow_out ) return flow_out; 95 + } 96 + } 100 97 } 98 + blocked[v] = (flow_out==0); 99 + return flow_out; 100 + } 101 +}; 101 102 103 +class DancingParty { public: 104 + int maxDances(vector <string> likes, int k) 105 + { 106 + const int n = likes.size(); 102 107 for(int M=1; M<=n; ++M) { 103 - // Flow 104 - flow_graph F = {}; 105 - for(int i=0; i<n; ++i) { 106 - F[SRC][L(i)] = M; 107 - F[L(i)][YL(i)] = M; 108 - F[L(i)][NL(i)] = k; 108 + typedef pair<int,int> Vert; 109 + auto_ptr< MaxFlow<Vert, int> > mf(new MaxFlow<Vert, int>); 109 110 110 - F[R(i)][DST] = M; 111 - F[YR(i)][R(i)] = M; 112 - F[NR(i)][R(i)] = k; 111 + for(int i=0; i<n; ++i) { 112 + mf->addEdge(Vert(0,0), Vert(1,i), M); // src L 113 + mf->addEdge(Vert(1,i), Vert(2,i), M); // L YL 114 + mf->addEdge(Vert(1,i), Vert(3,i), k); // L NL 115 + mf->addEdge(Vert(4,i), Vert(6,i), M); // YR R 116 + mf->addEdge(Vert(5,i), Vert(6,i), k); // NR R 117 + mf->addEdge(Vert(6,i), Vert(7,0), M); // R dst 113 118 114 119 for(int j=0; j<n; ++j) 115 120 if( likes[i][j] == 'Y' ) 116 - F[YL(i)][YR(j)] = 1; 121 + mf->addEdge(Vert(2,i), Vert(4,j), 1); 117 122 else 118 - F[NL(i)][NR(j)] = 1; 123 + mf->addEdge(Vert(3,i), Vert(5,j), 1); 119 124 } 120 125 121 - // Maxflow 122 - if( dinic(G, F, SRC, DST) < M*n ) 126 + if( mf->calc(Vert(0,0), Vert(7,0)) < M*n ) 123 127 return M-1; 124 128 } 125 129 return n; 126 130 } 127 131 }; 132 + 133 +// BEGIN CUT HERE 134 +#include <ctime> 135 +double start_time; string timer() 136 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 137 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 138 + { os << "{ "; 139 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 140 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 141 +void verify_case(const int& Expected, const int& Received) { 142 + bool ok = (Expected == Received); 143 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 144 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 145 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 146 +#define END verify_case(_, DancingParty().maxDances(likes, k));} 147 +int main(){ 148 + 149 +CASE(0) 150 + string likes_[] = {"YYY", "YYY", "YYY"}; 151 + vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 152 + int k = 0; 153 + int _ = 3; 154 +END 155 +CASE(1) 156 + string likes_[] = {"YYY", "YYN", "YNY"}; 157 + vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 158 + int k = 0; 159 + int _ = 2; 160 +END 161 +CASE(2) 162 + string likes_[] = {"YN", "YN"}; 163 + vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 164 + int k = 0; 165 + int _ = 0; 166 +END 167 +CASE(3) 168 + string likes_[] = {"YN", "YN"}; 169 + vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 170 + int k = 1; 171 + int _ = 1; 172 +END 173 +/* 174 +CASE(4) 175 + string likes_[] = ; 176 + vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 177 + int k = ; 178 + int _ = ; 179 +END 180 +CASE(5) 181 + string likes_[] = ; 182 + vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 183 + int k = ; 184 + int _ = ; 185 +END 186 +*/ 187 +} 188 +// END CUT HERE