Artifact 6a23b64e61d31ffbe2ad5288cab11361674ad7d6:
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 35 31 32 3e 0a 63 6c 61 73 73 20 4d NV=512>.class M
02f0: 61 78 46 6c 6f 77 0a 7b 0a 09 49 64 47 65 6e 3c axFlow.{..IdGen<
0300: 56 65 72 74 3e 20 69 64 67 65 6e 3b 0a 09 76 65 Vert> idgen;..ve
0310: 63 74 6f 72 3c 69 6e 74 3e 20 47 5b 4e 56 5d 3b ctor<int> G[NV];
0320: 0a 09 46 6c 6f 77 20 46 5b 4e 56 5d 5b 4e 56 5d ..Flow F[NV][NV]
0330: 3b 0a 0a 70 75 62 6c 69 63 3a 0a 09 76 6f 69 64 ;..public:..void
0340: 20 61 64 64 45 64 67 65 28 20 56 65 72 74 20 73 addEdge( Vert s
0350: 5f 2c 20 56 65 72 74 20 74 5f 2c 20 46 6c 6f 77 _, Vert t_, Flow
0360: 20 66 20 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 20 f )..{...const
0370: 69 6e 74 20 73 20 3d 20 69 64 67 65 6e 2e 76 32 int s = idgen.v2
0380: 69 64 28 73 5f 29 2c 20 74 20 3d 20 69 64 67 65 id(s_), t = idge
0390: 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 09 47 5b n.v2id(t_);...G[
03a0: 73 5d 2e 70 75 73 68 5f 62 61 63 6b 28 74 29 3b s].push_back(t);
03b0: 0a 09 09 47 5b 74 5d 2e 70 75 73 68 5f 62 61 63 ...G[t].push_bac
03c0: 6b 28 73 29 3b 0a 09 09 46 5b 73 5d 5b 74 5d 20 k(s);...F[s][t]
03d0: 3d 20 66 3b 0a 09 09 46 5b 74 5d 5b 73 5d 20 3d = f;...F[t][s] =
03e0: 20 30 3b 0a 09 7d 0a 0a 09 46 6c 6f 77 20 63 61 0;..}...Flow ca
03f0: 6c 63 28 20 56 65 72 74 20 73 5f 2c 20 56 65 72 lc( Vert s_, Ver
0400: 74 20 74 5f 20 29 0a 09 7b 0a 09 09 63 6f 6e 73 t t_ )..{...cons
0410: 74 20 69 6e 74 20 53 20 3d 20 69 64 67 65 6e 2e t int S = idgen.
0420: 76 32 69 64 28 73 5f 29 2c 20 44 20 3d 20 69 64 v2id(s_), D = id
0430: 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 09 gen.v2id(t_);...
0440: 66 6f 72 28 20 46 6c 6f 77 20 74 6f 74 61 6c 3d for( Flow total=
0450: 30 20 3b 3b 20 29 20 7b 0a 09 09 09 2f 2f 20 44 0 ;; ) {....// D
0460: 6f 20 42 46 53 20 61 6e 64 20 63 6f 6d 70 75 74 o BFS and comput
0470: 65 20 74 68 65 20 6c 65 76 65 6c 20 66 6f 72 20 e the level for
0480: 65 61 63 68 20 6e 6f 64 65 2e 0a 09 09 09 69 6e each node.....in
0490: 74 20 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b 0a t LV[NV] = {0};.
04a0: 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 ...vector<int> Q
04b0: 28 31 2c 20 53 29 3b 0a 09 09 09 66 6f 72 28 69 (1, S);....for(i
04c0: 6e 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d 70 74 nt lv=1; !Q.empt
04d0: 79 28 29 3b 20 2b 2b 6c 76 29 20 7b 0a 09 09 09 y(); ++lv) {....
04e0: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 32 3b .vector<int> Q2;
04f0: 0a 09 09 09 09 66 6f 72 28 73 69 7a 65 5f 74 20 .....for(size_t
0500: 69 3d 30 3b 20 69 21 3d 51 2e 73 69 7a 65 28 29 i=0; i!=Q.size()
0510: 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 63 6f ; ++i) {......co
0520: 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e 74 3e 26 nst vector<int>&
0530: 20 6e 65 20 3d 20 47 5b 51 5b 69 5d 5d 3b 0a 09 ne = G[Q[i]];..
0540: 09 09 09 09 66 6f 72 28 73 69 7a 65 5f 74 20 6a ....for(size_t j
0550: 3d 30 3b 20 6a 21 3d 6e 65 2e 73 69 7a 65 28 29 =0; j!=ne.size()
0560: 3b 20 2b 2b 6a 29 0a 09 09 09 09 09 09 69 66 28 ; ++j).......if(
0570: 20 46 5b 51 5b 69 5d 5d 5b 6e 65 5b 6a 5d 5d 20 F[Q[i]][ne[j]]
0580: 26 26 20 21 4c 56 5b 6e 65 5b 6a 5d 5d 20 26 26 && !LV[ne[j]] &&
0590: 20 6e 65 5b 6a 5d 21 3d 53 20 29 0a 09 09 09 09 ne[j]!=S ).....
05a0: 09 09 09 4c 56 5b 6e 65 5b 6a 5d 5d 3d 6c 76 2c ...LV[ne[j]]=lv,
05b0: 20 51 32 2e 70 75 73 68 5f 62 61 63 6b 28 6e 65 Q2.push_back(ne
05c0: 5b 6a 5d 29 3b 0a 09 09 09 09 7d 0a 09 09 09 09 [j]);.....}.....
05d0: 51 2e 73 77 61 70 28 51 32 29 3b 0a 09 09 09 7d Q.swap(Q2);....}
05e0: 0a 0a 09 09 09 2f 2f 20 44 65 73 74 69 6e 61 74 .....// Destinat
05f0: 69 6f 6e 20 69 73 20 6e 6f 77 20 75 6e 72 65 61 ion is now unrea
0600: 63 68 61 62 6c 65 2e 20 44 6f 6e 65 2e 0a 09 09 chable. Done....
0610: 09 69 66 28 20 21 4c 56 5b 44 5d 20 29 0a 09 09 .if( !LV[D] )...
0620: 09 09 72 65 74 75 72 6e 20 74 6f 74 61 6c 3b 0a ..return total;.
0630: 0a 09 09 09 2f 2f 20 49 74 65 72 61 74 69 6e 67 ....// Iterating
0640: 20 44 46 53 2e 0a 09 09 09 62 6f 6f 6c 20 62 6c DFS.....bool bl
0650: 6f 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b 0a ocked[NV] = {};.
0660: 09 09 09 74 6f 74 61 6c 20 2b 3d 20 64 69 6e 69 ...total += dini
0670: 63 5f 64 66 73 28 20 53 2c 20 44 2c 20 4c 56 2c c_dfs( S, D, LV,
0680: 20 30 78 37 66 66 66 66 66 66 66 2c 20 62 6c 6f 0x7fffffff, blo
0690: 63 6b 65 64 20 29 3b 0a 09 09 7d 0a 09 7d 0a 0a cked );...}..}..
06a0: 70 72 69 76 61 74 65 3a 0a 09 46 6c 6f 77 20 64 private:..Flow d
06b0: 69 6e 69 63 5f 64 66 73 28 20 69 6e 74 20 76 2c inic_dfs( int v,
06c0: 20 69 6e 74 20 44 2c 20 69 6e 74 20 4c 56 5b 5d int D, int LV[]
06d0: 2c 20 46 6c 6f 77 20 66 6c 6f 77 5f 69 6e 2c 20 , Flow flow_in,
06e0: 62 6f 6f 6c 20 62 6c 6f 63 6b 65 64 5b 5d 20 29 bool blocked[] )
06f0: 0a 09 7b 0a 09 09 46 6c 6f 77 20 66 6c 6f 77 5f ..{...Flow flow_
0700: 6f 75 74 20 3d 20 30 3b 0a 09 09 66 6f 72 28 73 out = 0;...for(s
0710: 69 7a 65 5f 74 20 69 3d 30 3b 20 69 21 3d 47 5b ize_t i=0; i!=G[
0720: 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 v].size(); ++i)
0730: 7b 0a 09 09 09 69 6e 74 20 75 20 3d 20 47 5b 76 {....int u = G[v
0740: 5d 5b 69 5d 3b 0a 09 09 09 69 66 28 20 4c 56 5b ][i];....if( LV[
0750: 76 5d 2b 31 3d 3d 4c 56 5b 75 5d 20 26 26 20 46 v]+1==LV[u] && F
0760: 5b 76 5d 5b 75 5d 20 29 20 7b 0a 09 09 09 09 46 [v][u] ) {.....F
0770: 6c 6f 77 20 66 20 3d 20 6d 69 6e 28 66 6c 6f 77 low f = min(flow
0780: 5f 69 6e 2d 66 6c 6f 77 5f 6f 75 74 2c 20 46 5b _in-flow_out, F[
0790: 76 5d 5b 75 5d 29 3b 0a 09 09 09 09 69 66 28 20 v][u]);.....if(
07a0: 75 3d 3d 44 20 7c 7c 20 21 62 6c 6f 63 6b 65 64 u==D || !blocked
07b0: 5b 75 5d 20 26 26 20 28 66 3d 64 69 6e 69 63 5f [u] && (f=dinic_
07c0: 64 66 73 28 75 2c 44 2c 4c 56 2c 66 2c 62 6c 6f dfs(u,D,LV,f,blo
07d0: 63 6b 65 64 29 29 3e 30 20 29 20 7b 0a 09 09 09 cked))>0 ) {....
07e0: 09 09 46 5b 76 5d 5b 75 5d 20 20 2d 3d 20 66 3b ..F[v][u] -= f;
07f0: 0a 09 09 09 09 09 46 5b 75 5d 5b 76 5d 20 20 2b ......F[u][v] +
0800: 3d 20 66 3b 0a 09 09 09 09 09 66 6c 6f 77 5f 6f = f;......flow_o
0810: 75 74 20 2b 3d 20 66 3b 0a 09 09 09 09 09 69 66 ut += f;......if
0820: 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 66 6c 6f ( flow_in == flo
0830: 77 5f 6f 75 74 20 29 20 72 65 74 75 72 6e 20 66 w_out ) return f
0840: 6c 6f 77 5f 6f 75 74 3b 0a 09 09 09 09 7d 0a 09 low_out;.....}..
0850: 09 09 7d 0a 09 09 7d 0a 09 09 62 6c 6f 63 6b 65 ..}...}...blocke
0860: 64 5b 76 5d 20 3d 20 28 66 6c 6f 77 5f 6f 75 74 d[v] = (flow_out
0870: 3d 3d 30 29 3b 0a 09 09 72 65 74 75 72 6e 20 66 ==0);...return f
0880: 6c 6f 77 5f 6f 75 74 3b 0a 09 7d 0a 7d 3b 0a low_out;..}.};.