5919ac5f24 2012-05-20 kinaba: #include <iostream> 5919ac5f24 2012-05-20 kinaba: #include <sstream> 5919ac5f24 2012-05-20 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 5919ac5f24 2012-05-20 kinaba: #include <map> 5919ac5f24 2012-05-20 kinaba: #include <set> 5919ac5f24 2012-05-20 kinaba: #include <algorithm> 5919ac5f24 2012-05-20 kinaba: #include <numeric> 5919ac5f24 2012-05-20 kinaba: #include <iterator> 5919ac5f24 2012-05-20 kinaba: #include <memory> 5919ac5f24 2012-05-20 kinaba: #include <functional> 5919ac5f24 2012-05-20 kinaba: #include <complex> 5919ac5f24 2012-05-20 kinaba: #include <queue> 5919ac5f24 2012-05-20 kinaba: #include <stack> 5919ac5f24 2012-05-20 kinaba: #include <cmath> 5919ac5f24 2012-05-20 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 5919ac5f24 2012-05-20 kinaba: typedef long long LL; 5919ac5f24 2012-05-20 kinaba: typedef long double LD; 5919ac5f24 2012-05-20 kinaba: typedef complex<LD> CMP; 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: template<typename T> 5919ac5f24 2012-05-20 kinaba: class IdGen 4fd800b3a8 2011-02-23 kinaba: { 5919ac5f24 2012-05-20 kinaba: map<T, int> v2id_; 5919ac5f24 2012-05-20 kinaba: vector<T> id2v_; 5919ac5f24 2012-05-20 kinaba: public: 5919ac5f24 2012-05-20 kinaba: int v2id(const T& v) { 5919ac5f24 2012-05-20 kinaba: if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 5919ac5f24 2012-05-20 kinaba: return v2id_[v]; 4fd800b3a8 2011-02-23 kinaba: } 5919ac5f24 2012-05-20 kinaba: const T& id2v(int i) const { return id2v_[i]; } 5919ac5f24 2012-05-20 kinaba: int size() const { return id2v_.size(); } 5919ac5f24 2012-05-20 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: template<typename Vert, typename Flow, int NV=512> 5919ac5f24 2012-05-20 kinaba: class MaxFlow 4fd800b3a8 2011-02-23 kinaba: { 5919ac5f24 2012-05-20 kinaba: IdGen<Vert> idgen; 5919ac5f24 2012-05-20 kinaba: vector<int> G[NV]; 5919ac5f24 2012-05-20 kinaba: Flow F[NV][NV]; 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: public: 5919ac5f24 2012-05-20 kinaba: void addEdge( Vert s_, Vert t_, Flow f ) 5919ac5f24 2012-05-20 kinaba: { 5919ac5f24 2012-05-20 kinaba: const int s = idgen.v2id(s_), t = idgen.v2id(t_); 5919ac5f24 2012-05-20 kinaba: G[s].push_back(t); 5919ac5f24 2012-05-20 kinaba: G[t].push_back(s); 5919ac5f24 2012-05-20 kinaba: F[s][t] = f; 5919ac5f24 2012-05-20 kinaba: F[t][s] = 0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: Flow calc( Vert s_, Vert t_ ) 4fd800b3a8 2011-02-23 kinaba: { 5919ac5f24 2012-05-20 kinaba: const int S = idgen.v2id(s_), D = idgen.v2id(t_); 5919ac5f24 2012-05-20 kinaba: for( Flow total=0 ;; ) { 5919ac5f24 2012-05-20 kinaba: // Do BFS and compute the level for each node. 5919ac5f24 2012-05-20 kinaba: int LV[NV] = {0}; 5919ac5f24 2012-05-20 kinaba: vector<int> Q(1, S); 5919ac5f24 2012-05-20 kinaba: for(int lv=1; !Q.empty(); ++lv) { 5919ac5f24 2012-05-20 kinaba: vector<int> Q2; 5919ac5f24 2012-05-20 kinaba: for(size_t i=0; i!=Q.size(); ++i) { 5919ac5f24 2012-05-20 kinaba: const vector<int>& ne = G[Q[i]]; 5919ac5f24 2012-05-20 kinaba: for(size_t j=0; j!=ne.size(); ++j) 5919ac5f24 2012-05-20 kinaba: if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S ) 5919ac5f24 2012-05-20 kinaba: LV[ne[j]]=lv, Q2.push_back(ne[j]); 5919ac5f24 2012-05-20 kinaba: } 5919ac5f24 2012-05-20 kinaba: Q.swap(Q2); 5919ac5f24 2012-05-20 kinaba: } 5919ac5f24 2012-05-20 kinaba: 5919ac5f24 2012-05-20 kinaba: // Destination is now unreachable. Done. 5919ac5f24 2012-05-20 kinaba: if( !LV[D] ) 5919ac5f24 2012-05-20 kinaba: return total; 5919ac5f24 2012-05-20 kinaba: 5919ac5f24 2012-05-20 kinaba: // Iterating DFS. 5919ac5f24 2012-05-20 kinaba: bool blocked[NV] = {}; 5919ac5f24 2012-05-20 kinaba: total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); 5919ac5f24 2012-05-20 kinaba: } 5919ac5f24 2012-05-20 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: private: 5919ac5f24 2012-05-20 kinaba: Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 5919ac5f24 2012-05-20 kinaba: { 5919ac5f24 2012-05-20 kinaba: Flow flow_out = 0; 5919ac5f24 2012-05-20 kinaba: for(size_t i=0; i!=G[v].size(); ++i) { 5919ac5f24 2012-05-20 kinaba: int u = G[v][i]; 5919ac5f24 2012-05-20 kinaba: if( LV[v]+1==LV[u] && F[v][u] ) { 5919ac5f24 2012-05-20 kinaba: Flow f = min(flow_in-flow_out, F[v][u]); 5919ac5f24 2012-05-20 kinaba: if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) { 5919ac5f24 2012-05-20 kinaba: F[v][u] -= f; 5919ac5f24 2012-05-20 kinaba: F[u][v] += f; 5919ac5f24 2012-05-20 kinaba: flow_out += f; 5919ac5f24 2012-05-20 kinaba: if( flow_in == flow_out ) return flow_out; 5919ac5f24 2012-05-20 kinaba: } 5919ac5f24 2012-05-20 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 5919ac5f24 2012-05-20 kinaba: blocked[v] = (flow_out==0); 5919ac5f24 2012-05-20 kinaba: return flow_out; 5919ac5f24 2012-05-20 kinaba: } 5919ac5f24 2012-05-20 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: class DancingParty { public: 5919ac5f24 2012-05-20 kinaba: int maxDances(vector <string> likes, int k) 5919ac5f24 2012-05-20 kinaba: { 5919ac5f24 2012-05-20 kinaba: const int n = likes.size(); 4fd800b3a8 2011-02-23 kinaba: for(int M=1; M<=n; ++M) { 5919ac5f24 2012-05-20 kinaba: typedef pair<int,int> Vert; 5919ac5f24 2012-05-20 kinaba: auto_ptr< MaxFlow<Vert, int> > mf(new MaxFlow<Vert, int>); 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: for(int i=0; i<n; ++i) { 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(0,0), Vert(1,i), M); // src L 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(1,i), Vert(2,i), M); // L YL 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(1,i), Vert(3,i), k); // L NL 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(4,i), Vert(6,i), M); // YR R 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(5,i), Vert(6,i), k); // NR R 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(6,i), Vert(7,0), M); // R dst 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' ) 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(2,i), Vert(4,j), 1); 4fd800b3a8 2011-02-23 kinaba: else 5919ac5f24 2012-05-20 kinaba: mf->addEdge(Vert(3,i), Vert(5,j), 1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 5919ac5f24 2012-05-20 kinaba: if( mf->calc(Vert(0,0), Vert(7,0)) < 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: }; 5919ac5f24 2012-05-20 kinaba: 5919ac5f24 2012-05-20 kinaba: // BEGIN CUT HERE 5919ac5f24 2012-05-20 kinaba: #include <ctime> 5919ac5f24 2012-05-20 kinaba: double start_time; string timer() 5919ac5f24 2012-05-20 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 5919ac5f24 2012-05-20 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 5919ac5f24 2012-05-20 kinaba: { os << "{ "; 5919ac5f24 2012-05-20 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 5919ac5f24 2012-05-20 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 5919ac5f24 2012-05-20 kinaba: void verify_case(const int& Expected, const int& Received) { 5919ac5f24 2012-05-20 kinaba: bool ok = (Expected == Received); 5919ac5f24 2012-05-20 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 5919ac5f24 2012-05-20 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 5919ac5f24 2012-05-20 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 5919ac5f24 2012-05-20 kinaba: #define END verify_case(_, DancingParty().maxDances(likes, k));} 5919ac5f24 2012-05-20 kinaba: int main(){ 5919ac5f24 2012-05-20 kinaba: 5919ac5f24 2012-05-20 kinaba: CASE(0) 5919ac5f24 2012-05-20 kinaba: string likes_[] = {"YYY", "YYY", "YYY"}; 5919ac5f24 2012-05-20 kinaba: vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 5919ac5f24 2012-05-20 kinaba: int k = 0; 5919ac5f24 2012-05-20 kinaba: int _ = 3; 5919ac5f24 2012-05-20 kinaba: END 5919ac5f24 2012-05-20 kinaba: CASE(1) 5919ac5f24 2012-05-20 kinaba: string likes_[] = {"YYY", "YYN", "YNY"}; 5919ac5f24 2012-05-20 kinaba: vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 5919ac5f24 2012-05-20 kinaba: int k = 0; 5919ac5f24 2012-05-20 kinaba: int _ = 2; 5919ac5f24 2012-05-20 kinaba: END 5919ac5f24 2012-05-20 kinaba: CASE(2) 5919ac5f24 2012-05-20 kinaba: string likes_[] = {"YN", "YN"}; 5919ac5f24 2012-05-20 kinaba: vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 5919ac5f24 2012-05-20 kinaba: int k = 0; 5919ac5f24 2012-05-20 kinaba: int _ = 0; 5919ac5f24 2012-05-20 kinaba: END 5919ac5f24 2012-05-20 kinaba: CASE(3) 5919ac5f24 2012-05-20 kinaba: string likes_[] = {"YN", "YN"}; 5919ac5f24 2012-05-20 kinaba: vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 5919ac5f24 2012-05-20 kinaba: int k = 1; 5919ac5f24 2012-05-20 kinaba: int _ = 1; 5919ac5f24 2012-05-20 kinaba: END 5919ac5f24 2012-05-20 kinaba: /* 5919ac5f24 2012-05-20 kinaba: CASE(4) 5919ac5f24 2012-05-20 kinaba: string likes_[] = ; 5919ac5f24 2012-05-20 kinaba: vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 5919ac5f24 2012-05-20 kinaba: int k = ; 5919ac5f24 2012-05-20 kinaba: int _ = ; 5919ac5f24 2012-05-20 kinaba: END 5919ac5f24 2012-05-20 kinaba: CASE(5) 5919ac5f24 2012-05-20 kinaba: string likes_[] = ; 5919ac5f24 2012-05-20 kinaba: vector <string> likes(likes_, likes_+sizeof(likes_)/sizeof(*likes_)); 5919ac5f24 2012-05-20 kinaba: int k = ; 5919ac5f24 2012-05-20 kinaba: int _ = ; 5919ac5f24 2012-05-20 kinaba: END 5919ac5f24 2012-05-20 kinaba: */ 5919ac5f24 2012-05-20 kinaba: } 5919ac5f24 2012-05-20 kinaba: // END CUT HERE