> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> 1 #include <vector> 4 #include <vector> 2 #include <string> 5 #include <string> 3 #include <iostream> | 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> 4 #include <cstring> | 16 #include <cmath> > 17 #include <cassert> 5 using namespace std; 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; | 26 map<T, int> v2id_; 22 for(int i=0; i!=G[v].size(); ++i) | 27 vector<T> id2v_; 23 { < > 28 public: 24 int u = G[v][i]; | 29 int v2id(const T& v) { 25 if( LV[v]+1==LV[u] && F[v][u] ) | 30 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } 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,blo < 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 } < > 31 return v2id_[v]; 36 } 32 } 37 blocked[v] = (flow_out==0); | 33 const T& id2v(int i) const { return id2v_[i]; } 38 return flow_out; | 34 int size() const { return id2v_.size(); } 39 } | 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 ;; ) { | 40 IdGen<Vert> idgen; 44 int LV[NV] = {0}; < 45 vector<int> Q(1, S); < 46 for(int lv=1; !Q.empty(); ++lv) < 47 { < 48 vector<int> Q2; | 41 vector<int> G[NV]; 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 < 54 LV[ne[j]]=lv, Q2.push_back(ne[j] < 55 } < 56 Q.swap(Q2); < 57 } < > 42 Flow F[NV][NV]; 58 43 59 if( !LV[D] ) | 44 public: 60 return total; | 45 void addEdge( Vert s_, Vert t_, Flow f ) 61 | 46 { 62 int blocked[NV] = {}; | 47 const int s = idgen.v2id(s_), t = idgen.v2id(t_); 63 total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked ); | 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(); | 56 const int S = idgen.v2id(s_), D = idgen.v2id(t_); 74 #define SRC 0 | 57 for( Flow total=0 ;; ) { 75 #define DST 1 | 58 // Do BFS and compute the level for each node. 76 #define L(i) 2+n*0+i | 59 int LV[NV] = {0}; 77 #define R(i) 2+n*1+i | 60 vector<int> Q(1, S); 78 #define YL(i) 2+n*2+i | 61 for(int lv=1; !Q.empty(); ++lv) { 79 #define NL(i) 2+n*3+i | 62 vector<int> Q2; 80 #define YR(i) 2+n*4+i | 63 for(size_t i=0; i!=Q.size(); ++i) { 81 #define NR(i) 2+n*5+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]] > 67 LV[ne[j]]=lv, Q2.push_ba > 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); | 82 private: > 83 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 84 | 84 { 85 // Graph < 86 for(int i=0; i<n; ++i) { | 85 Flow flow_out = 0; 87 G[SRC ].push_back(L(i)); G[L(i) ].push_back(SRC); | 86 for(size_t i=0; i!=G[v].size(); ++i) { 88 G[L(i)].push_back(YL(i)); G[YL(i)].push_back(L(i)); | 87 int u = G[v][i]; 89 G[L(i)].push_back(NL(i)); G[NL(i)].push_back(L(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 > 91 F[v][u] -= f; > 92 F[u][v] += f; > 93 flow_out += f; > 94 if( flow_in == flow_out ) return flow_ou 90 | 95 } 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 | 96 } 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 < 98 else < 99 G[NL(i)].push_back(NR(j)), G[NR(j)].push < 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 for(int M=1; M<=n; ++M) { 107 for(int M=1; M<=n; ++M) { 103 // Flow | 108 typedef pair<int,int> Vert; 104 flow_graph F = {}; | 109 auto_ptr< MaxFlow<Vert, int> > mf(new MaxFlow<Vert, int> 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; < 109 110 110 F[R(i)][DST] = M; | 111 for(int i=0; i<n; ++i) { 111 F[YR(i)][R(i)] = M; | 112 mf->addEdge(Vert(0,0), Vert(1,i), M); // src L 112 F[NR(i)][R(i)] = k; | 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 for(int j=0; j<n; ++j) 119 for(int j=0; j<n; ++j) 115 if( likes[i][j] == 'Y' ) 120 if( likes[i][j] == 'Y' ) 116 F[YL(i)][YR(j)] = 1; | 121 mf->addEdge(Vert(2,i), Vert(4,j) 117 else 122 else 118 F[NL(i)][NR(j)] = 1; | 123 mf->addEdge(Vert(3,i), Vert(5,j) 119 } 124 } 120 125 121 // Maxflow | 126 if( mf->calc(Vert(0,0), Vert(7,0)) < M*n ) 122 if( dinic(G, F, SRC, DST) < M*n ) < 123 return M-1; 127 return M-1; 124 } 128 } 125 return n; 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) > 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 > 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() > 144 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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