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

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

     2      2   //-------------------------------------------------------------
     3      3   // Dinic's Algorithm
     4      4   //   O(V E)
     5      5   //
     6      6   // G : bidirectional (G[i].has(j) <==> G[j].has(i))
     7      7   // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0
     8      8   //
     9         -// Verified by
            9  +// Old versoin 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   //   - SRM 543 Div1 LV3
    15     15   //-------------------------------------------------------------
    16     16   
................................................................................

    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=2048>
           31  +template<typename Vert, typename Flow, int NV=50*50*8+2>
    32     32   class MaxFlow
    33     33   {
           34  + typedef int Edge;
           35  +
           36  + vector<int>  G[NV];
           37  + vector<Flow> F;
           38  +
    34     39    IdGen<Vert> idgen;
    35         - vector<int> G[NV];
    36         - Flow F[NV][NV];
           40  + map<pair<int,int>, Edge> edge_id;
           41  + vector<int>  Edge_to;
           42  + vector<Edge> Edge_rev;
    37     43   
    38     44   public:
    39         - void addEdge( Vert s_, Vert t_, Flow f )
           45  + void add( Vert s_, Vert t_, Flow f )
    40     46    {
    41     47     const int s = idgen.v2id(s_), t = idgen.v2id(t_);
    42         -  G[s].push_back(t);
    43         -  G[t].push_back(s);
    44         -  F[s][t] = f;
    45         -  F[t][s] = 0;
           48  +  if(!edge_id.count(make_pair(s,t))) {
           49  +   const int e = int(edge_id.size());
           50  +   edge_id[make_pair(s,t)] = e;
           51  +   edge_id[make_pair(t,s)] = e+1;
           52  +   G[s].push_back(e);
           53  +   G[t].push_back(e+1);
           54  +   F.push_back(0);
           55  +   F.push_back(0);
           56  +   Edge_rev.push_back(e+1);
           57  +   Edge_rev.push_back(e);
           58  +   Edge_to.push_back(t);
           59  +   Edge_to.push_back(s);
           60  +  }
           61  +  const Edge e = edge_id[make_pair(s,t)];
           62  +  F[e] = min(F[e]+f, INF);
    46     63    }
    47     64   
    48     65    Flow calc( Vert s_, Vert t_ )
    49     66    {
    50     67     const int S = idgen.v2id(s_), D = idgen.v2id(t_);
    51     68     for( Flow total=0 ;; ) {
    52     69      // Do BFS and compute the level for each node.
    53     70      int LV[NV] = {0};
    54     71      vector<int> Q(1, S);
    55     72      for(int lv=1; !Q.empty(); ++lv) {
    56     73       vector<int> Q2;
    57     74       for(size_t i=0; i!=Q.size(); ++i) {
    58         -     const vector<int>& ne = G[Q[i]];
    59         -     for(size_t j=0; j!=ne.size(); ++j)
    60         -      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
    61         -       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           75  +     const vector<Edge>& ne = G[Q[i]];
           76  +     for(size_t j=0; j!=ne.size(); ++j) {
           77  +      Edge e = ne[j];
           78  +      int  t = Edge_to[e];
           79  +      if( F[e] && !LV[t] && t!=S )
           80  +       LV[t]=lv, Q2.push_back(t);
           81  +     }
    62     82       }
    63     83       Q.swap(Q2);
    64     84      }
    65     85   
    66     86      // Destination is now unreachable. Done.
    67     87      if( !LV[D] )
    68     88       return total;
    69     89   
    70     90      // Iterating DFS.
    71     91      bool blocked[NV] = {};
    72         -   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           92  +   total += dinic_dfs( S, D, LV, INF, blocked );
    73     93     }
    74     94    }
    75     95   
    76     96   private:
    77     97    Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
    78     98    {
    79     99     Flow flow_out = 0;
    80    100     for(size_t i=0; i!=G[v].size(); ++i) {
    81         -   int u = G[v][i];
    82         -   if( LV[v]+1==LV[u] && F[v][u] ) {
    83         -    Flow f = min(flow_in-flow_out, F[v][u]);
          101  +   Edge e = G[v][i];
          102  +   int  u = Edge_to[e];
          103  +   if( LV[v]+1==LV[u] && F[e] ) {
          104  +    Flow f = min(flow_in-flow_out, F[e]);
    84    105       if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
    85         -     F[v][u]  -= f;
    86         -     F[u][v]  += f;
          106  +     F[e]           -= f;
          107  +     F[Edge_rev[e]] += f;
    87    108        flow_out += f;
    88    109        if( flow_in == flow_out ) return flow_out;
    89    110       }
    90    111      }
    91    112     }
    92    113     blocked[v] = (flow_out==0);
    93    114     return flow_out;
    94    115    }
    95    116   };