Artifact f71eec6e87c84091a249f6be60467b84f910c81b:
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 4f 6c 64 20 76 65 72 73 6f 69 6e 20 .// Old versoin
00e0: 56 65 72 69 66 69 65 64 20 62 79 0a 2f 2f 20 20 Verified by.//
00f0: 20 2d 20 53 52 4d 20 33 39 39 20 44 69 76 31 20 - SRM 399 Div1
0100: 4c 56 33 0a 2f 2f 20 20 20 2d 20 50 4b 55 20 31 LV3.// - PKU 1
0110: 34 35 39 0a 2f 2f 20 20 20 2d 20 43 6f 64 65 43 459.// - CodeC
0120: 72 61 66 74 20 30 39 20 43 55 54 53 0a 2f 2f 20 raft 09 CUTS.//
0130: 20 20 2d 20 53 52 4d 20 34 36 35 20 44 69 76 31 - SRM 465 Div1
0140: 20 4c 56 32 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 LV2.// - SRM
0150: 35 34 33 20 44 69 76 31 20 4c 56 33 0a 2f 2f 2d 543 Div1 LV3.//-
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: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 74 65 ------------..te
01a0: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
01b0: 54 3e 0a 63 6c 61 73 73 20 49 64 47 65 6e 0a 7b T>.class IdGen.{
01c0: 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e 20 76 32 ..map<T, int> v2
01d0: 69 64 5f 3b 0a 09 76 65 63 74 6f 72 3c 54 3e 20 id_;..vector<T>
01e0: 20 20 69 64 32 76 5f 3b 0a 70 75 62 6c 69 63 3a id2v_;.public:
01f0: 0a 09 69 6e 74 20 76 32 69 64 28 63 6f 6e 73 74 ..int v2id(const
0200: 20 54 26 20 76 29 20 7b 0a 09 09 69 66 28 20 21 T& v) {...if( !
0210: 76 32 69 64 5f 2e 63 6f 75 6e 74 28 76 29 20 29 v2id_.count(v) )
0220: 20 7b 20 76 32 69 64 5f 5b 76 5d 20 3d 20 73 69 { v2id_[v] = si
0230: 7a 65 28 29 3b 20 69 64 32 76 5f 2e 70 75 73 68 ze(); id2v_.push
0240: 5f 62 61 63 6b 28 76 29 3b 20 7d 0a 09 09 72 65 _back(v); }...re
0250: 74 75 72 6e 20 76 32 69 64 5f 5b 76 5d 3b 0a 09 turn v2id_[v];..
0260: 7d 0a 09 63 6f 6e 73 74 20 54 26 20 69 64 32 76 }..const T& id2v
0270: 28 69 6e 74 20 69 29 20 63 6f 6e 73 74 20 7b 20 (int i) const {
0280: 72 65 74 75 72 6e 20 69 64 32 76 5f 5b 69 5d 3b return id2v_[i];
0290: 20 7d 0a 09 69 6e 74 20 73 69 7a 65 28 29 20 63 }..int size() c
02a0: 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 69 64 onst { return id
02b0: 32 76 5f 2e 73 69 7a 65 28 29 3b 20 7d 0a 7d 3b 2v_.size(); }.};
02c0: 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e ..template<typen
02d0: 61 6d 65 20 56 65 72 74 2c 20 74 79 70 65 6e 61 ame Vert, typena
02e0: 6d 65 20 46 6c 6f 77 2c 20 69 6e 74 20 4e 56 3d me Flow, int NV=
02f0: 35 30 2a 35 30 2a 38 2b 32 3e 0a 63 6c 61 73 73 50*50*8+2>.class
0300: 20 4d 61 78 46 6c 6f 77 0a 7b 0a 09 74 79 70 65 MaxFlow.{..type
0310: 64 65 66 20 69 6e 74 20 45 64 67 65 3b 0a 0a 09 def int Edge;...
0320: 76 65 63 74 6f 72 3c 69 6e 74 3e 20 20 47 5b 4e vector<int> G[N
0330: 56 5d 3b 0a 09 76 65 63 74 6f 72 3c 46 6c 6f 77 V];..vector<Flow
0340: 3e 20 46 3b 0a 0a 09 49 64 47 65 6e 3c 56 65 72 > F;...IdGen<Ver
0350: 74 3e 20 69 64 67 65 6e 3b 0a 09 6d 61 70 3c 70 t> idgen;..map<p
0360: 61 69 72 3c 69 6e 74 2c 69 6e 74 3e 2c 20 45 64 air<int,int>, Ed
0370: 67 65 3e 20 65 64 67 65 5f 69 64 3b 0a 09 76 65 ge> edge_id;..ve
0380: 63 74 6f 72 3c 69 6e 74 3e 20 20 45 64 67 65 5f ctor<int> Edge_
0390: 74 6f 3b 0a 09 76 65 63 74 6f 72 3c 45 64 67 65 to;..vector<Edge
03a0: 3e 20 45 64 67 65 5f 72 65 76 3b 0a 0a 70 75 62 > Edge_rev;..pub
03b0: 6c 69 63 3a 0a 09 76 6f 69 64 20 61 64 64 28 20 lic:..void add(
03c0: 56 65 72 74 20 73 5f 2c 20 56 65 72 74 20 74 5f Vert s_, Vert t_
03d0: 2c 20 46 6c 6f 77 20 66 20 29 0a 09 7b 0a 09 09 , Flow f )..{...
03e0: 63 6f 6e 73 74 20 69 6e 74 20 73 20 3d 20 69 64 const int s = id
03f0: 67 65 6e 2e 76 32 69 64 28 73 5f 29 2c 20 74 20 gen.v2id(s_), t
0400: 3d 20 69 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 = idgen.v2id(t_)
0410: 3b 0a 09 09 69 66 28 21 65 64 67 65 5f 69 64 2e ;...if(!edge_id.
0420: 63 6f 75 6e 74 28 6d 61 6b 65 5f 70 61 69 72 28 count(make_pair(
0430: 73 2c 74 29 29 29 20 7b 0a 09 09 09 63 6f 6e 73 s,t))) {....cons
0440: 74 20 69 6e 74 20 65 20 3d 20 69 6e 74 28 65 64 t int e = int(ed
0450: 67 65 5f 69 64 2e 73 69 7a 65 28 29 29 3b 0a 09 ge_id.size());..
0460: 09 09 65 64 67 65 5f 69 64 5b 6d 61 6b 65 5f 70 ..edge_id[make_p
0470: 61 69 72 28 73 2c 74 29 5d 20 3d 20 65 3b 0a 09 air(s,t)] = e;..
0480: 09 09 65 64 67 65 5f 69 64 5b 6d 61 6b 65 5f 70 ..edge_id[make_p
0490: 61 69 72 28 74 2c 73 29 5d 20 3d 20 65 2b 31 3b air(t,s)] = e+1;
04a0: 0a 09 09 09 47 5b 73 5d 2e 70 75 73 68 5f 62 61 ....G[s].push_ba
04b0: 63 6b 28 65 29 3b 0a 09 09 09 47 5b 74 5d 2e 70 ck(e);....G[t].p
04c0: 75 73 68 5f 62 61 63 6b 28 65 2b 31 29 3b 0a 09 ush_back(e+1);..
04d0: 09 09 46 2e 70 75 73 68 5f 62 61 63 6b 28 30 29 ..F.push_back(0)
04e0: 3b 0a 09 09 09 46 2e 70 75 73 68 5f 62 61 63 6b ;....F.push_back
04f0: 28 30 29 3b 0a 09 09 09 45 64 67 65 5f 72 65 76 (0);....Edge_rev
0500: 2e 70 75 73 68 5f 62 61 63 6b 28 65 2b 31 29 3b .push_back(e+1);
0510: 0a 09 09 09 45 64 67 65 5f 72 65 76 2e 70 75 73 ....Edge_rev.pus
0520: 68 5f 62 61 63 6b 28 65 29 3b 0a 09 09 09 45 64 h_back(e);....Ed
0530: 67 65 5f 74 6f 2e 70 75 73 68 5f 62 61 63 6b 28 ge_to.push_back(
0540: 74 29 3b 0a 09 09 09 45 64 67 65 5f 74 6f 2e 70 t);....Edge_to.p
0550: 75 73 68 5f 62 61 63 6b 28 73 29 3b 0a 09 09 7d ush_back(s);...}
0560: 0a 09 09 63 6f 6e 73 74 20 45 64 67 65 20 65 20 ...const Edge e
0570: 3d 20 65 64 67 65 5f 69 64 5b 6d 61 6b 65 5f 70 = edge_id[make_p
0580: 61 69 72 28 73 2c 74 29 5d 3b 0a 09 09 46 5b 65 air(s,t)];...F[e
0590: 5d 20 3d 20 6d 69 6e 28 46 5b 65 5d 2b 66 2c 20 ] = min(F[e]+f,
05a0: 49 4e 46 29 3b 0a 09 7d 0a 0a 09 46 6c 6f 77 20 INF);..}...Flow
05b0: 63 61 6c 63 28 20 56 65 72 74 20 73 5f 2c 20 56 calc( Vert s_, V
05c0: 65 72 74 20 74 5f 20 29 0a 09 7b 0a 09 09 63 6f ert t_ )..{...co
05d0: 6e 73 74 20 69 6e 74 20 53 20 3d 20 69 64 67 65 nst int S = idge
05e0: 6e 2e 76 32 69 64 28 73 5f 29 2c 20 44 20 3d 20 n.v2id(s_), D =
05f0: 69 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0a idgen.v2id(t_);.
0600: 09 09 66 6f 72 28 20 46 6c 6f 77 20 74 6f 74 61 ..for( Flow tota
0610: 6c 3d 30 20 3b 3b 20 29 20 7b 0a 09 09 09 2f 2f l=0 ;; ) {....//
0620: 20 44 6f 20 42 46 53 20 61 6e 64 20 63 6f 6d 70 Do BFS and comp
0630: 75 74 65 20 74 68 65 20 6c 65 76 65 6c 20 66 6f ute the level fo
0640: 72 20 65 61 63 68 20 6e 6f 64 65 2e 0a 09 09 09 r each node.....
0650: 69 6e 74 20 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d int LV[NV] = {0}
0660: 3b 0a 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e ;....vector<int>
0670: 20 51 28 31 2c 20 53 29 3b 0a 09 09 09 66 6f 72 Q(1, S);....for
0680: 28 69 6e 74 20 6c 76 3d 31 3b 20 21 51 2e 65 6d (int lv=1; !Q.em
0690: 70 74 79 28 29 3b 20 2b 2b 6c 76 29 20 7b 0a 09 pty(); ++lv) {..
06a0: 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 ...vector<int> Q
06b0: 32 3b 0a 09 09 09 09 66 6f 72 28 73 69 7a 65 5f 2;.....for(size_
06c0: 74 20 69 3d 30 3b 20 69 21 3d 51 2e 73 69 7a 65 t i=0; i!=Q.size
06d0: 28 29 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 (); ++i) {......
06e0: 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 45 64 67 const vector<Edg
06f0: 65 3e 26 20 6e 65 20 3d 20 47 5b 51 5b 69 5d 5d e>& ne = G[Q[i]]
0700: 3b 0a 09 09 09 09 09 66 6f 72 28 73 69 7a 65 5f ;......for(size_
0710: 74 20 6a 3d 30 3b 20 6a 21 3d 6e 65 2e 73 69 7a t j=0; j!=ne.siz
0720: 65 28 29 3b 20 2b 2b 6a 29 20 7b 0a 09 09 09 09 e(); ++j) {.....
0730: 09 09 45 64 67 65 20 65 20 3d 20 6e 65 5b 6a 5d ..Edge e = ne[j]
0740: 3b 0a 09 09 09 09 09 09 69 6e 74 20 20 74 20 3d ;.......int t =
0750: 20 45 64 67 65 5f 74 6f 5b 65 5d 3b 0a 09 09 09 Edge_to[e];....
0760: 09 09 09 69 66 28 20 46 5b 65 5d 20 26 26 20 21 ...if( F[e] && !
0770: 4c 56 5b 74 5d 20 26 26 20 74 21 3d 53 20 29 0a LV[t] && t!=S ).
0780: 09 09 09 09 09 09 09 4c 56 5b 74 5d 3d 6c 76 2c .......LV[t]=lv,
0790: 20 51 32 2e 70 75 73 68 5f 62 61 63 6b 28 74 29 Q2.push_back(t)
07a0: 3b 0a 09 09 09 09 09 7d 0a 09 09 09 09 7d 0a 09 ;......}.....}..
07b0: 09 09 09 51 2e 73 77 61 70 28 51 32 29 3b 0a 09 ...Q.swap(Q2);..
07c0: 09 09 7d 0a 0a 09 09 09 2f 2f 20 44 65 73 74 69 ..}.....// Desti
07d0: 6e 61 74 69 6f 6e 20 69 73 20 6e 6f 77 20 75 6e nation is now un
07e0: 72 65 61 63 68 61 62 6c 65 2e 20 44 6f 6e 65 2e reachable. Done.
07f0: 0a 09 09 09 69 66 28 20 21 4c 56 5b 44 5d 20 29 ....if( !LV[D] )
0800: 0a 09 09 09 09 72 65 74 75 72 6e 20 74 6f 74 61 .....return tota
0810: 6c 3b 0a 0a 09 09 09 2f 2f 20 49 74 65 72 61 74 l;.....// Iterat
0820: 69 6e 67 20 44 46 53 2e 0a 09 09 09 62 6f 6f 6c ing DFS.....bool
0830: 20 62 6c 6f 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b blocked[NV] = {
0840: 7d 3b 0a 09 09 09 74 6f 74 61 6c 20 2b 3d 20 64 };....total += d
0850: 69 6e 69 63 5f 64 66 73 28 20 53 2c 20 44 2c 20 inic_dfs( S, D,
0860: 4c 56 2c 20 49 4e 46 2c 20 62 6c 6f 63 6b 65 64 LV, INF, blocked
0870: 20 29 3b 0a 09 09 7d 0a 09 7d 0a 0a 70 72 69 76 );...}..}..priv
0880: 61 74 65 3a 0a 09 46 6c 6f 77 20 64 69 6e 69 63 ate:..Flow dinic
0890: 5f 64 66 73 28 20 69 6e 74 20 76 2c 20 69 6e 74 _dfs( int v, int
08a0: 20 44 2c 20 69 6e 74 20 4c 56 5b 5d 2c 20 46 6c D, int LV[], Fl
08b0: 6f 77 20 66 6c 6f 77 5f 69 6e 2c 20 62 6f 6f 6c ow flow_in, bool
08c0: 20 62 6c 6f 63 6b 65 64 5b 5d 20 29 0a 09 7b 0a blocked[] )..{.
08d0: 09 09 46 6c 6f 77 20 66 6c 6f 77 5f 6f 75 74 20 ..Flow flow_out
08e0: 3d 20 30 3b 0a 09 09 66 6f 72 28 73 69 7a 65 5f = 0;...for(size_
08f0: 74 20 69 3d 30 3b 20 69 21 3d 47 5b 76 5d 2e 73 t i=0; i!=G[v].s
0900: 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0a 09 09 ize(); ++i) {...
0910: 09 45 64 67 65 20 65 20 3d 20 47 5b 76 5d 5b 69 .Edge e = G[v][i
0920: 5d 3b 0a 09 09 09 69 6e 74 20 20 75 20 3d 20 45 ];....int u = E
0930: 64 67 65 5f 74 6f 5b 65 5d 3b 0a 09 09 09 69 66 dge_to[e];....if
0940: 28 20 4c 56 5b 76 5d 2b 31 3d 3d 4c 56 5b 75 5d ( LV[v]+1==LV[u]
0950: 20 26 26 20 46 5b 65 5d 20 29 20 7b 0a 09 09 09 && F[e] ) {....
0960: 09 46 6c 6f 77 20 66 20 3d 20 6d 69 6e 28 66 6c .Flow f = min(fl
0970: 6f 77 5f 69 6e 2d 66 6c 6f 77 5f 6f 75 74 2c 20 ow_in-flow_out,
0980: 46 5b 65 5d 29 3b 0a 09 09 09 09 69 66 28 20 75 F[e]);.....if( u
0990: 3d 3d 44 20 7c 7c 20 21 62 6c 6f 63 6b 65 64 5b ==D || !blocked[
09a0: 75 5d 20 26 26 20 28 66 3d 64 69 6e 69 63 5f 64 u] && (f=dinic_d
09b0: 66 73 28 75 2c 44 2c 4c 56 2c 66 2c 62 6c 6f 63 fs(u,D,LV,f,bloc
09c0: 6b 65 64 29 29 3e 30 20 29 20 7b 0a 09 09 09 09 ked))>0 ) {.....
09d0: 09 46 5b 65 5d 20 20 20 20 20 20 20 20 20 20 20 .F[e]
09e0: 2d 3d 20 66 3b 0a 09 09 09 09 09 46 5b 45 64 67 -= f;......F[Edg
09f0: 65 5f 72 65 76 5b 65 5d 5d 20 2b 3d 20 66 3b 0a e_rev[e]] += f;.
0a00: 09 09 09 09 09 66 6c 6f 77 5f 6f 75 74 20 2b 3d .....flow_out +=
0a10: 20 66 3b 0a 09 09 09 09 09 69 66 28 20 66 6c 6f f;......if( flo
0a20: 77 5f 69 6e 20 3d 3d 20 66 6c 6f 77 5f 6f 75 74 w_in == flow_out
0a30: 20 29 20 72 65 74 75 72 6e 20 66 6c 6f 77 5f 6f ) return flow_o
0a40: 75 74 3b 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09 ut;.....}....}..
0a50: 09 7d 0a 09 09 62 6c 6f 63 6b 65 64 5b 76 5d 20 .}...blocked[v]
0a60: 3d 20 28 66 6c 6f 77 5f 6f 75 74 3d 3d 30 29 3b = (flow_out==0);
0a70: 0a 09 09 72 65 74 75 72 6e 20 66 6c 6f 77 5f 6f ...return flow_o
0a80: 75 74 3b 0a 09 7d 0a 7d 3b 0a ut;..}.};.