Artifact aeb9a52588e83f01ff7727a3f63b0b6170b5d0b0:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 44 69 6e 69 63 27 73 20 41 6c 67 6f .// Dinic's Algo
0050: 72 69 74 68 6d 0a 2f 2f 20 20 20 4f 28 56 20 45 rithm.// O(V E
0060: 29 0a 2f 2f 0a 2f 2f 20 47 20 3a 20 62 69 64 69 ).//.// G : bidi
0070: 72 65 63 74 69 6f 6e 61 6c 20 28 47 5b 69 5d 2e rectional (G[i].
0080: 68 61 73 28 6a 29 20 3c 3d 3d 3e 20 47 5b 6a 5d has(j) <==> G[j]
0090: 2e 68 61 73 28 69 29 29 0a 2f 2f 20 46 20 3a 20 .has(i)).// F :
00a0: 66 6c 6f 77 2d 63 61 70 61 63 69 74 79 20 46 5b flow-capacity F[
00b0: 69 5d 5b 6a 5d 20 3d 20 43 61 70 61 63 69 74 79 i][j] = Capacity
00c0: 2c 20 46 5b 6a 5d 5b 69 5d 20 3d 20 30 0a 2f 2f , F[j][i] = 0.//
00d0: 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 0a .// Verified by.
00e0: 2f 2f 20 20 20 2d 20 53 52 4d 20 33 39 39 20 44 // - SRM 399 D
00f0: 69 76 31 20 4c 56 33 0a 2f 2f 20 20 20 2d 20 50 iv1 LV3.// - P
0100: 4b 55 20 31 34 35 39 0a 2f 2f 20 20 20 2d 20 43 KU 1459.// - C
0110: 6f 64 65 43 72 61 66 74 20 30 39 20 43 55 54 53 odeCraft 09 CUTS
0120: 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 34 36 35 20 .// - SRM 465
0130: 44 69 76 31 20 4c 56 32 0a 2f 2f 20 20 20 2d 20 Div1 LV2.// -
0140: 53 52 4d 20 35 34 33 20 44 69 76 31 20 4c 56 33 SRM 543 Div1 LV3
0150: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0160: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0170: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0180: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0190: 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e ..template<typen
01a0: 61 6d 65 20 54 3e 0a 63 6c 61 73 73 20 49 64 47 ame T>.class IdG
01b0: 65 6e 0a 7b 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 en.{..map<T, int
01c0: 3e 20 76 32 69 64 5f 3b 0a 09 76 65 63 74 6f 72 > v2id_;..vector
01d0: 3c 54 3e 20 20 20 69 64 32 76 5f 3b 0a 70 75 62 <T> id2v_;.pub
01e0: 6c 69 63 3a 0a 09 69 6e 74 20 76 32 69 64 28 63 lic:..int v2id(c
01f0: 6f 6e 73 74 20 54 26 20 76 29 20 7b 0a 09 09 69 onst T& v) {...i
0200: 66 28 20 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 f( !v2id_.count(
0210: 76 29 20 29 20 7b 20 76 32 69 64 5f 5b 76 5d 20 v) ) { v2id_[v]
0220: 3d 20 73 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e = size(); id2v_.
0230: 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 7d 0a push_back(v); }.
0240: 09 09 72 65 74 75 72 6e 20 76 32 69 64 5f 5b 76 ..return v2id_[v
0250: 5d 3b 0a 09 7d 0a 09 63 6f 6e 73 74 20 54 26 20 ];..}..const T&
0260: 69 64 32 76 28 69 6e 74 20 69 29 20 63 6f 6e 73 id2v(int i) cons
0270: 74 20 7b 20 72 65 74 75 72 6e 20 69 64 32 76 5f t { return id2v_
0280: 5b 69 5d 3b 20 7d 0a 09 69 6e 74 20 73 69 7a 65 [i]; }..int size
0290: 28 29 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 () const { retur
02a0: 6e 20 69 64 32 76 5f 2e 73 69 7a 65 28 29 3b 20 n id2v_.size();
02b0: 7d 0a 7d 3b 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 }.};..template<t
02c0: 79 70 65 6e 61 6d 65 20 56 65 72 74 2c 20 74 79 ypename Vert, ty
02d0: 70 65 6e 61 6d 65 20 46 6c 6f 77 2c 20 69 6e 74 pename Flow, int
02e0: 20 4e 56 3d 32 30 34 38 3e 0a 63 6c 61 73 73 20 NV=2048>.class
02f0: 4d 61 78 46 6c 6f 77 0a 7b 0a 09 49 64 47 65 6e MaxFlow.{..IdGen
0300: 3c 56 65 72 74 3e 20 69 64 67 65 6e 3b 0a 09 76 <Vert> idgen;..v
0310: 65 63 74 6f 72 3c 69 6e 74 3e 20 47 5b 4e 56 5d ector<int> G[NV]
0320: 3b 0a 09 46 6c 6f 77 20 46 5b 4e 56 5d 5b 4e 56 ;..Flow F[NV][NV
0330: 5d 3b 0a 0a 70 75 62 6c 69 63 3a 0a 09 76 6f 69 ];..public:..voi
0340: 64 20 61 64 64 45 64 67 65 28 20 56 65 72 74 20 d addEdge( Vert
0350: 73 5f 2c 20 56 65 72 74 20 74 5f 2c 20 46 6c 6f s_, Vert t_, Flo
0360: 77 20 66 20 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 w f )..{...const
0370: 20 69 6e 74 20 73 20 3d 20 69 64 67 65 6e 2e 76 int s = idgen.v
0380: 32 69 64 28 73 5f 29 2c 20 74 20 3d 20 69 64 67 2id(s_), t = idg
0390: 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 09 47 en.v2id(t_);...G
03a0: 5b 73 5d 2e 70 75 73 68 5f 62 61 63 6b 28 74 29 [s].push_back(t)
03b0: 3b 0a 09 09 47 5b 74 5d 2e 70 75 73 68 5f 62 61 ;...G[t].push_ba
03c0: 63 6b 28 73 29 3b 0a 09 09 46 5b 73 5d 5b 74 5d ck(s);...F[s][t]
03d0: 20 3d 20 66 3b 0a 09 09 46 5b 74 5d 5b 73 5d 20 = f;...F[t][s]
03e0: 3d 20 30 3b 0a 09 7d 0a 0a 09 46 6c 6f 77 20 63 = 0;..}...Flow c
03f0: 61 6c 63 28 20 56 65 72 74 20 73 5f 2c 20 56 65 alc( Vert s_, Ve
0400: 72 74 20 74 5f 20 29 0a 09 7b 0a 09 09 63 6f 6e rt t_ )..{...con
0410: 73 74 20 69 6e 74 20 53 20 3d 20 69 64 67 65 6e st int S = idgen
0420: 2e 76 32 69 64 28 73 5f 29 2c 20 44 20 3d 20 69 .v2id(s_), D = i
0430: 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 dgen.v2id(t_);..
0440: 09 66 6f 72 28 20 46 6c 6f 77 20 74 6f 74 61 6c .for( Flow total
0450: 3d 30 20 3b 3b 20 29 20 7b 0a 09 09 09 2f 2f 20 =0 ;; ) {....//
0460: 44 6f 20 42 46 53 20 61 6e 64 20 63 6f 6d 70 75 Do BFS and compu
0470: 74 65 20 74 68 65 20 6c 65 76 65 6c 20 66 6f 72 te the level for
0480: 20 65 61 63 68 20 6e 6f 64 65 2e 0a 09 09 09 69 each node.....i
0490: 6e 74 20 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b nt LV[NV] = {0};
04a0: 0a 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 ....vector<int>
04b0: 51 28 31 2c 20 53 29 3b 0a 09 09 09 66 6f 72 28 Q(1, S);....for(
04c0: 69 6e 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d 70 int lv=1; !Q.emp
04d0: 74 79 28 29 3b 20 2b 2b 6c 76 29 20 7b 0a 09 09 ty(); ++lv) {...
04e0: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 32 ..vector<int> Q2
04f0: 3b 0a 09 09 09 09 66 6f 72 28 73 69 7a 65 5f 74 ;.....for(size_t
0500: 20 69 3d 30 3b 20 69 21 3d 51 2e 73 69 7a 65 28 i=0; i!=Q.size(
0510: 29 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 63 ); ++i) {......c
0520: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e 74 3e onst vector<int>
0530: 26 20 6e 65 20 3d 20 47 5b 51 5b 69 5d 5d 3b 0a & ne = G[Q[i]];.
0540: 09 09 09 09 09 66 6f 72 28 73 69 7a 65 5f 74 20 .....for(size_t
0550: 6a 3d 30 3b 20 6a 21 3d 6e 65 2e 73 69 7a 65 28 j=0; j!=ne.size(
0560: 29 3b 20 2b 2b 6a 29 0a 09 09 09 09 09 09 69 66 ); ++j).......if
0570: 28 20 46 5b 51 5b 69 5d 5d 5b 6e 65 5b 6a 5d 5d ( F[Q[i]][ne[j]]
0580: 20 26 26 20 21 4c 56 5b 6e 65 5b 6a 5d 5d 20 26 && !LV[ne[j]] &
0590: 26 20 6e 65 5b 6a 5d 21 3d 53 20 29 0a 09 09 09 & ne[j]!=S )....
05a0: 09 09 09 09 4c 56 5b 6e 65 5b 6a 5d 5d 3d 6c 76 ....LV[ne[j]]=lv
05b0: 2c 20 51 32 2e 70 75 73 68 5f 62 61 63 6b 28 6e , Q2.push_back(n
05c0: 65 5b 6a 5d 29 3b 0a 09 09 09 09 7d 0a 09 09 09 e[j]);.....}....
05d0: 09 51 2e 73 77 61 70 28 51 32 29 3b 0a 09 09 09 .Q.swap(Q2);....
05e0: 7d 0a 0a 09 09 09 2f 2f 20 44 65 73 74 69 6e 61 }.....// Destina
05f0: 74 69 6f 6e 20 69 73 20 6e 6f 77 20 75 6e 72 65 tion is now unre
0600: 61 63 68 61 62 6c 65 2e 20 44 6f 6e 65 2e 0a 09 achable. Done...
0610: 09 09 69 66 28 20 21 4c 56 5b 44 5d 20 29 0a 09 ..if( !LV[D] )..
0620: 09 09 09 72 65 74 75 72 6e 20 74 6f 74 61 6c 3b ...return total;
0630: 0a 0a 09 09 09 2f 2f 20 49 74 65 72 61 74 69 6e .....// Iteratin
0640: 67 20 44 46 53 2e 0a 09 09 09 62 6f 6f 6c 20 62 g DFS.....bool b
0650: 6c 6f 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b locked[NV] = {};
0660: 0a 09 09 09 74 6f 74 61 6c 20 2b 3d 20 64 69 6e ....total += din
0670: 69 63 5f 64 66 73 28 20 53 2c 20 44 2c 20 4c 56 ic_dfs( S, D, LV
0680: 2c 20 30 78 37 66 66 66 66 66 66 66 2c 20 62 6c , 0x7fffffff, bl
0690: 6f 63 6b 65 64 20 29 3b 0a 09 09 7d 0a 09 7d 0a ocked );...}..}.
06a0: 0a 70 72 69 76 61 74 65 3a 0a 09 46 6c 6f 77 20 .private:..Flow
06b0: 64 69 6e 69 63 5f 64 66 73 28 20 69 6e 74 20 76 dinic_dfs( int v
06c0: 2c 20 69 6e 74 20 44 2c 20 69 6e 74 20 4c 56 5b , int D, int LV[
06d0: 5d 2c 20 46 6c 6f 77 20 66 6c 6f 77 5f 69 6e 2c ], Flow flow_in,
06e0: 20 62 6f 6f 6c 20 62 6c 6f 63 6b 65 64 5b 5d 20 bool blocked[]
06f0: 29 0a 09 7b 0a 09 09 46 6c 6f 77 20 66 6c 6f 77 )..{...Flow flow
0700: 5f 6f 75 74 20 3d 20 30 3b 0a 09 09 66 6f 72 28 _out = 0;...for(
0710: 73 69 7a 65 5f 74 20 69 3d 30 3b 20 69 21 3d 47 size_t i=0; i!=G
0720: 5b 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 [v].size(); ++i)
0730: 20 7b 0a 09 09 09 69 6e 74 20 75 20 3d 20 47 5b {....int u = G[
0740: 76 5d 5b 69 5d 3b 0a 09 09 09 69 66 28 20 4c 56 v][i];....if( LV
0750: 5b 76 5d 2b 31 3d 3d 4c 56 5b 75 5d 20 26 26 20 [v]+1==LV[u] &&
0760: 46 5b 76 5d 5b 75 5d 20 29 20 7b 0a 09 09 09 09 F[v][u] ) {.....
0770: 46 6c 6f 77 20 66 20 3d 20 6d 69 6e 28 66 6c 6f Flow f = min(flo
0780: 77 5f 69 6e 2d 66 6c 6f 77 5f 6f 75 74 2c 20 46 w_in-flow_out, F
0790: 5b 76 5d 5b 75 5d 29 3b 0a 09 09 09 09 69 66 28 [v][u]);.....if(
07a0: 20 75 3d 3d 44 20 7c 7c 20 21 62 6c 6f 63 6b 65 u==D || !blocke
07b0: 64 5b 75 5d 20 26 26 20 28 66 3d 64 69 6e 69 63 d[u] && (f=dinic
07c0: 5f 64 66 73 28 75 2c 44 2c 4c 56 2c 66 2c 62 6c _dfs(u,D,LV,f,bl
07d0: 6f 63 6b 65 64 29 29 3e 30 20 29 20 7b 0a 09 09 ocked))>0 ) {...
07e0: 09 09 09 46 5b 76 5d 5b 75 5d 20 20 2d 3d 20 66 ...F[v][u] -= f
07f0: 3b 0a 09 09 09 09 09 46 5b 75 5d 5b 76 5d 20 20 ;......F[u][v]
0800: 2b 3d 20 66 3b 0a 09 09 09 09 09 66 6c 6f 77 5f += f;......flow_
0810: 6f 75 74 20 2b 3d 20 66 3b 0a 09 09 09 09 09 69 out += f;......i
0820: 66 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 66 6c f( flow_in == fl
0830: 6f 77 5f 6f 75 74 20 29 20 72 65 74 75 72 6e 20 ow_out ) return
0840: 66 6c 6f 77 5f 6f 75 74 3b 0a 09 09 09 09 7d 0a flow_out;.....}.
0850: 09 09 09 7d 0a 09 09 7d 0a 09 09 62 6c 6f 63 6b ...}...}...block
0860: 65 64 5b 76 5d 20 3d 20 28 66 6c 6f 77 5f 6f 75 ed[v] = (flow_ou
0870: 74 3d 3d 30 29 3b 0a 09 09 72 65 74 75 72 6e 20 t==0);...return
0880: 66 6c 6f 77 5f 6f 75 74 3b 0a 09 7d 0a 7d 3b 0a flow_out;..}.};.