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

Modified CheckList.pptx from [dc7db7f8ce6a9e9f] to [f15f8f9b31b7d536].

cannot compute difference between binary files

Modified lib/graph/maxFlow.cpp from [c6d3325f9b7a789b] to [296b9275312ebbf1].

     9      9   // Verified by
    10     10   //   - SRM 399 Div1 LV3
    11     11   //   - PKU 1459
    12     12   //   - CodeCraft 09 CUTS
    13     13   //   - SRM 465 Div1 LV2
    14     14   //-------------------------------------------------------------
    15     15   
    16         -static const int NV = 512;
    17         -typedef int           flow;
    18         -typedef int           vert;
    19         -typedef vert          edge;
    20         -typedef vector<edge>  edges;
    21         -typedef vector<edges> graph;
    22         -typedef flow          flow_graph[NV][NV];
    23         -
    24         -flow dinic_dfs( graph& G, flow_graph F, vert v, vert D,
    25         -                int LV[], flow flow_in, int blocked[] )
           16  +template<typename T>
           17  +class IdGen
    26     18   {
    27         - flow flow_out = 0;
    28         - for(int i=0; i!=G[v].size(); ++i) {
    29         -  int u = G[v][i];
    30         -  if( LV[v]+1==LV[u] && F[v][u] ) {
    31         -   flow f = min(flow_in-flow_out, F[v][u]);
    32         -   if( u==D || !blocked[u] && (f=dinic_dfs(G,F,u,D,LV,f,blocked)) ) {
    33         -    F[v][u]  -= f;
    34         -    F[u][v]  += f;
    35         -    flow_out += f;
    36         -    if( flow_in == flow_out ) return flow_out;
    37         -   }
    38         -  }
           19  + map<T, int> v2id_;
           20  + vector<T>   id2v_;
           21  +public:
           22  + int v2id(const T& v) {
           23  +  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
           24  +  return v2id_[v];
    39     25    }
    40         - blocked[v] = (flow_out==0);
    41         - return flow_out;
    42         -}
           26  + const T& id2v(int i) const { return id2v_[i]; }
           27  + int size() const { return id2v_.size(); }
           28  +};
    43     29   
    44         -flow maxFlow( graph& G, flow_graph F, vert S, vert D )
           30  +template<typename Vert, typename Flow, int NV=512>
           31  +class MaxFlow
    45     32   {
    46         - for( flow total=0 ;; ) {
    47         -  int LV[NV] = {0};
    48         -  vector<int> Q(1, S);
    49         -  for(int lv=1; !Q.empty(); ++lv) {
    50         -   vector<int> Q2;
    51         -   for(int i=0; i!=Q.size(); ++i) {
    52         -    edges& ne = G[Q[i]];
    53         -    for(int j=0; j!=ne.size(); ++j)
    54         -     if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
    55         -      LV[ne[j]]=lv, Q2.push_back(ne[j]);
           33  + IdGen<Vert> idgen;
           34  + vector<int> G[NV];
           35  + Flow F[NV][NV];
           36  +
           37  +public:
           38  + void addEdge( Vert s_, Vert t_, Flow f )
           39  + {
           40  +  const int s = idgen.v2id(s_), t = idgen.v2id(t_);
           41  +  G[s].push_back(t);
           42  +  G[t].push_back(s);
           43  +  F[s][t] = f;
           44  +  F[t][s] = 0;
           45  + }
           46  +
           47  + Flow calc( Vert s_, Vert t_ )
           48  + {
           49  +  const int S = idgen.v2id(s_), D = idgen.v2id(t_);
           50  +  for( Flow total=0 ;; ) {
           51  +   // Do BFS and compute the level for each node.
           52  +   int LV[NV] = {0};
           53  +   vector<int> Q(1, S);
           54  +   for(int lv=1; !Q.empty(); ++lv) {
           55  +    vector<int> Q2;
           56  +    for(size_t i=0; i!=Q.size(); ++i) {
           57  +     const vector<int>& ne = G[Q[i]];
           58  +     for(size_t j=0; j!=ne.size(); ++j)
           59  +      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
           60  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           61  +    }
           62  +    Q.swap(Q2);
    56     63      }
    57         -   Q.swap(Q2);
    58         -  }
           64  +
           65  +   // Destination is now unreachable. Done.
           66  +   if( !LV[D] )
           67  +    return total;
    59     68   
    60         -  if( !LV[D] )
    61         -   return total;
           69  +   // Iterating DFS.
           70  +   bool blocked[NV] = {};
           71  +   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           72  +  }
           73  + }
    62     74   
    63         -  int blocked[NV] = {};
    64         -  total += dinic_dfs( G, F, S, D, LV, 0x7fffffff, blocked );
           75  +private:
           76  + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
           77  + {
           78  +  Flow flow_out = 0;
           79  +  for(size_t i=0; i!=G[v].size(); ++i) {
           80  +   int u = G[v][i];
           81  +   if( LV[v]+1==LV[u] && F[v][u] ) {
           82  +    Flow f = min(flow_in-flow_out, F[v][u]);
           83  +    if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
           84  +     F[v][u]  -= f;
           85  +     F[u][v]  += f;
           86  +     flow_out += f;
           87  +     if( flow_in == flow_out ) return flow_out;
           88  +    }
           89  +   }
           90  +  }
           91  +  blocked[v] = (flow_out==0);
           92  +  return flow_out;
    65     93    }
    66         -}
           94  +};