Artifact c6d3325f9b7a789bbab3583d479611ec8e40be05:
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 2d 2d 2d 2d 2d Div1 LV2.//-----
0140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0150: 2d 2d 2d 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 0a 0a 73 74 61 74 69 63 --------..static
0180: 20 63 6f 6e 73 74 20 69 6e 74 20 4e 56 20 3d 20 const int NV =
0190: 35 31 32 3b 0a 74 79 70 65 64 65 66 20 69 6e 74 512;.typedef int
01a0: 20 20 20 20 20 20 20 20 20 20 20 66 6c 6f 77 3b flow;
01b0: 0a 74 79 70 65 64 65 66 20 69 6e 74 20 20 20 20 .typedef int
01c0: 20 20 20 20 20 20 20 76 65 72 74 3b 0a 74 79 70 vert;.typ
01d0: 65 64 65 66 20 76 65 72 74 20 20 20 20 20 20 20 edef vert
01e0: 20 20 20 65 64 67 65 3b 0a 74 79 70 65 64 65 66 edge;.typedef
01f0: 20 76 65 63 74 6f 72 3c 65 64 67 65 3e 20 20 65 vector<edge> e
0200: 64 67 65 73 3b 0a 74 79 70 65 64 65 66 20 76 65 dges;.typedef ve
0210: 63 74 6f 72 3c 65 64 67 65 73 3e 20 67 72 61 70 ctor<edges> grap
0220: 68 3b 0a 74 79 70 65 64 65 66 20 66 6c 6f 77 20 h;.typedef flow
0230: 20 20 20 20 20 20 20 20 20 66 6c 6f 77 5f 67 72 flow_gr
0240: 61 70 68 5b 4e 56 5d 5b 4e 56 5d 3b 0a 0a 66 6c aph[NV][NV];..fl
0250: 6f 77 20 64 69 6e 69 63 5f 64 66 73 28 20 67 72 ow dinic_dfs( gr
0260: 61 70 68 26 20 47 2c 20 66 6c 6f 77 5f 67 72 61 aph& G, flow_gra
0270: 70 68 20 46 2c 20 76 65 72 74 20 76 2c 20 76 65 ph F, vert v, ve
0280: 72 74 20 44 2c 0a 20 20 20 20 20 20 20 20 20 20 rt D,.
0290: 20 20 20 20 20 20 69 6e 74 20 4c 56 5b 5d 2c 20 int LV[],
02a0: 66 6c 6f 77 20 66 6c 6f 77 5f 69 6e 2c 20 69 6e flow flow_in, in
02b0: 74 20 62 6c 6f 63 6b 65 64 5b 5d 20 29 0a 7b 0a t blocked[] ).{.
02c0: 09 66 6c 6f 77 20 66 6c 6f 77 5f 6f 75 74 20 3d .flow flow_out =
02d0: 20 30 3b 0a 09 66 6f 72 28 69 6e 74 20 69 3d 30 0;..for(int i=0
02e0: 3b 20 69 21 3d 47 5b 76 5d 2e 73 69 7a 65 28 29 ; i!=G[v].size()
02f0: 3b 20 2b 2b 69 29 20 7b 0a 09 09 69 6e 74 20 75 ; ++i) {...int u
0300: 20 3d 20 47 5b 76 5d 5b 69 5d 3b 0a 09 09 69 66 = G[v][i];...if
0310: 28 20 4c 56 5b 76 5d 2b 31 3d 3d 4c 56 5b 75 5d ( LV[v]+1==LV[u]
0320: 20 26 26 20 46 5b 76 5d 5b 75 5d 20 29 20 7b 0a && F[v][u] ) {.
0330: 09 09 09 66 6c 6f 77 20 66 20 3d 20 6d 69 6e 28 ...flow f = min(
0340: 66 6c 6f 77 5f 69 6e 2d 66 6c 6f 77 5f 6f 75 74 flow_in-flow_out
0350: 2c 20 46 5b 76 5d 5b 75 5d 29 3b 0a 09 09 09 69 , F[v][u]);....i
0360: 66 28 20 75 3d 3d 44 20 7c 7c 20 21 62 6c 6f 63 f( u==D || !bloc
0370: 6b 65 64 5b 75 5d 20 26 26 20 28 66 3d 64 69 6e ked[u] && (f=din
0380: 69 63 5f 64 66 73 28 47 2c 46 2c 75 2c 44 2c 4c ic_dfs(G,F,u,D,L
0390: 56 2c 66 2c 62 6c 6f 63 6b 65 64 29 29 20 29 20 V,f,blocked)) )
03a0: 7b 0a 09 09 09 09 46 5b 76 5d 5b 75 5d 20 20 2d {.....F[v][u] -
03b0: 3d 20 66 3b 0a 09 09 09 09 46 5b 75 5d 5b 76 5d = f;.....F[u][v]
03c0: 20 20 2b 3d 20 66 3b 0a 09 09 09 09 66 6c 6f 77 += f;.....flow
03d0: 5f 6f 75 74 20 2b 3d 20 66 3b 0a 09 09 09 09 69 _out += f;.....i
03e0: 66 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 66 6c f( flow_in == fl
03f0: 6f 77 5f 6f 75 74 20 29 20 72 65 74 75 72 6e 20 ow_out ) return
0400: 66 6c 6f 77 5f 6f 75 74 3b 0a 09 09 09 7d 0a 09 flow_out;....}..
0410: 09 7d 0a 09 7d 0a 09 62 6c 6f 63 6b 65 64 5b 76 .}..}..blocked[v
0420: 5d 20 3d 20 28 66 6c 6f 77 5f 6f 75 74 3d 3d 30 ] = (flow_out==0
0430: 29 3b 0a 09 72 65 74 75 72 6e 20 66 6c 6f 77 5f );..return flow_
0440: 6f 75 74 3b 0a 7d 0a 0a 66 6c 6f 77 20 6d 61 78 out;.}..flow max
0450: 46 6c 6f 77 28 20 67 72 61 70 68 26 20 47 2c 20 Flow( graph& G,
0460: 66 6c 6f 77 5f 67 72 61 70 68 20 46 2c 20 76 65 flow_graph F, ve
0470: 72 74 20 53 2c 20 76 65 72 74 20 44 20 29 0a 7b rt S, vert D ).{
0480: 0a 09 66 6f 72 28 20 66 6c 6f 77 20 74 6f 74 61 ..for( flow tota
0490: 6c 3d 30 20 3b 3b 20 29 20 7b 0a 09 09 69 6e 74 l=0 ;; ) {...int
04a0: 20 4c 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b 0a 09 LV[NV] = {0};..
04b0: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 51 28 31 .vector<int> Q(1
04c0: 2c 20 53 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 , S);...for(int
04d0: 6c 76 3d 31 3b 20 21 51 2e 65 6d 70 74 79 28 29 lv=1; !Q.empty()
04e0: 3b 20 2b 2b 6c 76 29 20 7b 0a 09 09 09 76 65 63 ; ++lv) {....vec
04f0: 74 6f 72 3c 69 6e 74 3e 20 51 32 3b 0a 09 09 09 tor<int> Q2;....
0500: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 21 3d for(int i=0; i!=
0510: 51 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b Q.size(); ++i) {
0520: 0a 09 09 09 09 65 64 67 65 73 26 20 6e 65 20 3d .....edges& ne =
0530: 20 47 5b 51 5b 69 5d 5d 3b 0a 09 09 09 09 66 6f G[Q[i]];.....fo
0540: 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 21 3d 6e 65 r(int j=0; j!=ne
0550: 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 0a 09 09 .size(); ++j)...
0560: 09 09 09 69 66 28 20 46 5b 51 5b 69 5d 5d 5b 6e ...if( F[Q[i]][n
0570: 65 5b 6a 5d 5d 20 26 26 20 21 4c 56 5b 6e 65 5b e[j]] && !LV[ne[
0580: 6a 5d 5d 20 26 26 20 6e 65 5b 6a 5d 21 3d 53 20 j]] && ne[j]!=S
0590: 29 0a 09 09 09 09 09 09 4c 56 5b 6e 65 5b 6a 5d ).......LV[ne[j]
05a0: 5d 3d 6c 76 2c 20 51 32 2e 70 75 73 68 5f 62 61 ]=lv, Q2.push_ba
05b0: 63 6b 28 6e 65 5b 6a 5d 29 3b 0a 09 09 09 7d 0a ck(ne[j]);....}.
05c0: 09 09 09 51 2e 73 77 61 70 28 51 32 29 3b 0a 09 ...Q.swap(Q2);..
05d0: 09 7d 0a 0a 09 09 69 66 28 20 21 4c 56 5b 44 5d .}....if( !LV[D]
05e0: 20 29 0a 09 09 09 72 65 74 75 72 6e 20 74 6f 74 )....return tot
05f0: 61 6c 3b 0a 0a 09 09 69 6e 74 20 62 6c 6f 63 6b al;....int block
0600: 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b 0a 09 09 74 ed[NV] = {};...t
0610: 6f 74 61 6c 20 2b 3d 20 64 69 6e 69 63 5f 64 66 otal += dinic_df
0620: 73 28 20 47 2c 20 46 2c 20 53 2c 20 44 2c 20 4c s( G, F, S, D, L
0630: 56 2c 20 30 78 37 66 66 66 66 66 66 66 2c 20 62 V, 0x7fffffff, b
0640: 6c 6f 63 6b 65 64 20 29 3b 0a 09 7d 0a 7d 0a locked );..}.}.