• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified SRM/399/1C.cpp from [b357fd2040b9449a] to [c3aca7366b0837d8].

            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

Modified lib/graph/maxFlow.cpp from [6a23b64e61d31ffb] to [aeb9a52588e83f01].

    24     24     if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
    25     25     return v2id_[v];
    26     26    }
    27     27    const T& id2v(int i) const { return id2v_[i]; }
    28     28    int size() const { return id2v_.size(); }
    29     29   };
    30     30   
    31         -template<typename Vert, typename Flow, int NV=512>
           31  +template<typename Vert, typename Flow, int NV=2048>
    32     32   class MaxFlow
    33     33   {
    34     34    IdGen<Vert> idgen;
    35     35    vector<int> G[NV];
    36     36    Flow F[NV][NV];
    37     37   
    38     38   public: