Artifact a86509e21e3c5ec5b764d64d77b393c4a019845e:
0000: 2f 2f 2d 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 0a ---------------.
0040: 2f 2f 20 4d 69 6e 43 6f 73 74 2d 4d 61 78 46 6c // MinCost-MaxFl
0050: 6f 77 0a 2f 2f 20 20 20 4f 28 3f 3f 29 0a 2f 2f ow.// O(??).//
0060: 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 0a .// Verified by.
0070: 2f 2f 20 20 20 2d 20 53 52 4d 20 34 38 37 20 44 // - SRM 487 D
0080: 69 76 32 20 4c 56 33 0a 2f 2f 20 20 20 2d 20 53 iv2 LV3.// - S
0090: 52 4d 20 34 39 31 20 44 69 76 31 20 4c 56 33 0a RM 491 Div1 LV3.
00a0: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
00b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
00e0: 0a 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 .#include <iostr
00f0: 65 61 6d 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 eam>.#include <s
0100: 74 72 69 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 tring>.#include
0110: 3c 76 65 63 74 6f 72 3e 0a 23 69 6e 63 6c 75 64 <vector>.#includ
0120: 65 20 3c 6d 61 70 3e 0a 23 69 6e 63 6c 75 64 65 e <map>.#include
0130: 20 3c 71 75 65 75 65 3e 0a 75 73 69 6e 67 20 6e <queue>.using n
0140: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0a 0a 74 amespace std;..t
0150: 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 emplate<typename
0160: 20 54 3e 0a 63 6c 61 73 73 20 49 64 47 65 6e 0a T>.class IdGen.
0170: 7b 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 3e 20 76 {..map<T, int> v
0180: 32 69 64 5f 3b 0a 09 76 65 63 74 6f 72 3c 54 3e 2id_;..vector<T>
0190: 20 20 20 69 64 32 76 5f 3b 0a 70 75 62 6c 69 63 id2v_;.public
01a0: 3a 0a 09 69 6e 74 20 76 32 69 64 28 63 6f 6e 73 :..int v2id(cons
01b0: 74 20 54 26 20 76 29 20 7b 0a 09 09 69 66 28 20 t T& v) {...if(
01c0: 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 76 29 20 !v2id_.count(v)
01d0: 29 20 7b 20 76 32 69 64 5f 5b 76 5d 20 3d 20 73 ) { v2id_[v] = s
01e0: 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e 70 75 73 ize(); id2v_.pus
01f0: 68 5f 62 61 63 6b 28 76 29 3b 20 7d 0a 09 09 72 h_back(v); }...r
0200: 65 74 75 72 6e 20 76 32 69 64 5f 5b 76 5d 3b 0a eturn v2id_[v];.
0210: 09 7d 0a 09 63 6f 6e 73 74 20 54 26 20 69 64 32 .}..const T& id2
0220: 76 28 69 6e 74 20 69 29 20 63 6f 6e 73 74 20 7b v(int i) const {
0230: 20 72 65 74 75 72 6e 20 69 64 32 76 5f 5b 69 5d return id2v_[i]
0240: 3b 20 7d 0a 09 69 6e 74 20 73 69 7a 65 28 29 20 ; }..int size()
0250: 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 69 const { return i
0260: 64 32 76 5f 2e 73 69 7a 65 28 29 3b 20 7d 0a 7d d2v_.size(); }.}
0270: 3b 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 ;..template<type
0280: 6e 61 6d 65 20 56 65 72 74 2c 20 74 79 70 65 6e name Vert, typen
0290: 61 6d 65 20 43 6f 73 74 2c 20 74 79 70 65 6e 61 ame Cost, typena
02a0: 6d 65 20 46 6c 6f 77 2c 20 69 6e 74 20 4e 56 3d me Flow, int NV=
02b0: 32 35 36 3e 0a 63 6c 61 73 73 20 4d 69 6e 43 6f 256>.class MinCo
02c0: 73 74 46 6c 6f 77 0a 7b 0a 09 49 64 47 65 6e 3c stFlow.{..IdGen<
02d0: 56 65 72 74 3e 20 69 64 67 65 6e 3b 0a 0a 09 76 Vert> idgen;...v
02e0: 65 63 74 6f 72 3c 69 6e 74 3e 20 47 5b 4e 56 5d ector<int> G[NV]
02f0: 3b 0a 09 46 6c 6f 77 20 46 5b 4e 56 5d 5b 4e 56 ;..Flow F[NV][NV
0300: 5d 3b 0a 09 43 6f 73 74 20 43 5b 4e 56 5d 5b 4e ];..Cost C[NV][N
0310: 56 5d 3b 0a 0a 70 75 62 6c 69 63 3a 0a 09 76 6f V];..public:..vo
0320: 69 64 20 61 64 64 45 64 67 65 28 20 56 65 72 74 id addEdge( Vert
0330: 20 73 5f 2c 20 56 65 72 74 20 74 5f 2c 20 43 6f s_, Vert t_, Co
0340: 73 74 20 63 2c 20 46 6c 6f 77 20 66 20 29 0a 09 st c, Flow f )..
0350: 7b 0a 09 09 69 6e 74 20 73 20 3d 20 69 64 67 65 {...int s = idge
0360: 6e 2e 76 32 69 64 28 73 5f 29 2c 20 74 20 3d 20 n.v2id(s_), t =
0370: 69 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b 0a idgen.v2id(t_);.
0380: 09 09 47 5b 73 5d 2e 70 75 73 68 5f 62 61 63 6b ..G[s].push_back
0390: 28 74 29 3b 0a 09 09 47 5b 74 5d 2e 70 75 73 68 (t);...G[t].push
03a0: 5f 62 61 63 6b 28 73 29 3b 0a 09 09 43 5b 73 5d _back(s);...C[s]
03b0: 5b 74 5d 20 3d 20 63 3b 0a 09 09 43 5b 74 5d 5b [t] = c;...C[t][
03c0: 73 5d 20 3d 20 2d 63 3b 0a 09 09 46 5b 73 5d 5b s] = -c;...F[s][
03d0: 74 5d 20 3d 20 66 3b 0a 09 09 46 5b 74 5d 5b 73 t] = f;...F[t][s
03e0: 5d 20 3d 20 30 3b 0a 09 7d 0a 0a 09 70 61 69 72 ] = 0;..}...pair
03f0: 3c 43 6f 73 74 2c 20 46 6c 6f 77 3e 20 63 61 6c <Cost, Flow> cal
0400: 63 28 20 56 65 72 74 20 73 5f 2c 20 56 65 72 74 c( Vert s_, Vert
0410: 20 74 5f 20 29 0a 09 7b 0a 09 09 63 6f 6e 73 74 t_ )..{...const
0420: 20 69 6e 74 20 4e 3d 69 64 67 65 6e 2e 73 69 7a int N=idgen.siz
0430: 65 28 29 2c 20 53 3d 69 64 67 65 6e 2e 76 32 69 e(), S=idgen.v2i
0440: 64 28 73 5f 29 2c 20 54 3d 69 64 67 65 6e 2e 76 d(s_), T=idgen.v
0450: 32 69 64 28 74 5f 29 3b 0a 09 09 73 74 61 74 69 2id(t_);...stati
0460: 63 20 63 6f 6e 73 74 20 43 6f 73 74 20 43 4f 53 c const Cost COS
0470: 54 5f 49 4e 46 20 3d 20 31 65 2b 33 30 30 3b 20 T_INF = 1e+300;
0480: 2f 2f 20 21 21 45 44 49 54 20 48 45 52 45 21 21 // !!EDIT HERE!!
0490: 0a 09 09 73 74 61 74 69 63 20 63 6f 6e 73 74 20 ...static const
04a0: 46 6c 6f 77 20 46 4c 4f 57 5f 49 4e 46 20 3d 20 Flow FLOW_INF =
04b0: 30 78 37 66 66 66 66 66 66 66 3b 0a 0a 09 09 43 0x7fffffff;....C
04c0: 6f 73 74 20 74 6f 74 61 6c 5f 63 6f 73 74 20 3d ost total_cost =
04d0: 20 30 3b 0a 09 09 46 6c 6f 77 20 74 6f 74 61 6c 0;...Flow total
04e0: 5f 66 6c 6f 77 20 3d 20 30 3b 0a 09 09 76 65 63 _flow = 0;...vec
04f0: 74 6f 72 3c 43 6f 73 74 3e 20 68 28 4e 2c 20 30 tor<Cost> h(N, 0
0500: 29 3b 20 2f 2f 20 70 6f 74 65 6e 74 69 61 6c 0a ); // potential.
0510: 09 09 66 6f 72 28 46 6c 6f 77 20 52 46 3d 46 4c ..for(Flow RF=FL
0520: 4f 57 5f 49 4e 46 3b 20 52 46 3e 30 3b 20 29 20 OW_INF; RF>0; )
0530: 2f 2f 20 72 65 73 69 64 75 61 6c 20 66 6c 6f 77 // residual flow
0540: 0a 09 09 7b 0a 09 09 09 2f 2f 20 44 69 6a 6b 73 ...{....// Dijks
0550: 74 72 61 20 2d 2d 20 66 69 6e 64 20 74 68 65 20 tra -- find the
0560: 6d 69 6e 2d 63 6f 73 74 20 70 61 74 68 0a 09 09 min-cost path...
0570: 09 76 65 63 74 6f 72 3c 43 6f 73 74 3e 20 64 28 .vector<Cost> d(
0580: 4e 2c 20 43 4f 53 54 5f 49 4e 46 29 3b 20 20 64 N, COST_INF); d
0590: 5b 53 5d 20 3d 20 30 3b 0a 09 09 09 76 65 63 74 [S] = 0;....vect
05a0: 6f 72 3c 69 6e 74 3e 20 20 70 72 65 76 28 4e 2c or<int> prev(N,
05b0: 20 2d 31 29 3b 0a 0a 09 09 09 74 79 70 65 64 65 -1);.....typede
05c0: 66 20 70 61 69 72 3c 20 43 6f 73 74 2c 20 70 61 f pair< Cost, pa
05d0: 69 72 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 63 65 ir<int,int> > ce
05e0: 64 67 65 3b 0a 09 09 09 70 72 69 6f 72 69 74 79 dge;....priority
05f0: 5f 71 75 65 75 65 3c 20 63 65 64 67 65 2c 20 76 _queue< cedge, v
0600: 65 63 74 6f 72 3c 63 65 64 67 65 3e 2c 20 67 72 ector<cedge>, gr
0610: 65 61 74 65 72 3c 63 65 64 67 65 3e 20 3e 20 51 eater<cedge> > Q
0620: 3b 0a 09 09 09 51 2e 70 75 73 68 28 20 63 65 64 ;....Q.push( ced
0630: 67 65 28 30 2c 20 6d 61 6b 65 5f 70 61 69 72 28 ge(0, make_pair(
0640: 53 2c 53 29 29 20 29 3b 0a 09 09 09 77 68 69 6c S,S)) );....whil
0650: 65 28 20 21 51 2e 65 6d 70 74 79 28 29 20 29 20 e( !Q.empty() )
0660: 7b 0a 09 09 09 09 63 65 64 67 65 20 65 20 3d 20 {.....cedge e =
0670: 51 2e 74 6f 70 28 29 3b 20 51 2e 70 6f 70 28 29 Q.top(); Q.pop()
0680: 3b 0a 09 09 09 09 69 66 28 20 70 72 65 76 5b 65 ;.....if( prev[e
0690: 2e 73 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 5d 20 .second.second]
06a0: 3e 3d 20 30 20 29 0a 09 09 09 09 09 63 6f 6e 74 >= 0 )......cont
06b0: 69 6e 75 65 3b 0a 09 09 09 09 70 72 65 76 5b 65 inue;.....prev[e
06c0: 2e 73 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 5d 20 .second.second]
06d0: 3d 20 65 2e 73 65 63 6f 6e 64 2e 66 69 72 73 74 = e.second.first
06e0: 3b 0a 0a 09 09 09 09 69 6e 74 20 75 20 3d 20 65 ;......int u = e
06f0: 2e 73 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 3b 0a .second.second;.
0700: 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b ....for(int i=0;
0710: 20 69 3c 47 5b 75 5d 2e 73 69 7a 65 28 29 3b 20 i<G[u].size();
0720: 2b 2b 69 29 20 7b 0a 09 09 09 09 09 69 6e 74 20 ++i) {......int
0730: 20 76 20 3d 20 47 5b 75 5d 5b 69 5d 3b 0a 09 09 v = G[u][i];...
0740: 09 09 09 43 6f 73 74 20 72 5f 63 6f 73 74 20 3d ...Cost r_cost =
0750: 20 43 5b 75 5d 5b 76 5d 20 2b 20 68 5b 75 5d 20 C[u][v] + h[u]
0760: 2d 20 68 5b 76 5d 3b 0a 09 09 09 09 09 69 66 28 - h[v];......if(
0770: 20 46 5b 75 5d 5b 76 5d 20 3e 20 30 20 26 26 20 F[u][v] > 0 &&
0780: 64 5b 76 5d 20 3e 20 64 5b 75 5d 2b 72 5f 63 6f d[v] > d[u]+r_co
0790: 73 74 20 29 0a 09 09 09 09 09 09 51 2e 70 75 73 st ).......Q.pus
07a0: 68 28 20 63 65 64 67 65 28 64 5b 76 5d 3d 64 5b h( cedge(d[v]=d[
07b0: 75 5d 2b 72 5f 63 6f 73 74 2c 20 6d 61 6b 65 5f u]+r_cost, make_
07c0: 70 61 69 72 28 75 2c 76 29 29 20 29 3b 0a 09 09 pair(u,v)) );...
07d0: 09 09 7d 0a 09 09 09 7d 0a 0a 09 09 09 69 66 28 ..}....}.....if(
07e0: 20 70 72 65 76 5b 54 5d 20 3c 20 30 20 29 0a 09 prev[T] < 0 )..
07f0: 09 09 09 62 72 65 61 6b 3b 20 2f 2f 20 46 69 6e ...break; // Fin
0800: 69 73 68 65 64 0a 0a 09 09 09 2f 2f 20 52 75 6e ished.....// Run
0810: 20 74 68 65 20 66 6c 6f 77 20 61 73 20 6d 75 63 the flow as muc
0820: 68 20 61 73 20 70 6f 73 73 69 62 6c 65 0a 09 09 h as possible...
0830: 09 46 6c 6f 77 20 66 20 3d 20 52 46 3b 0a 09 09 .Flow f = RF;...
0840: 09 66 6f 72 28 69 6e 74 20 75 3d 54 3b 20 75 21 .for(int u=T; u!
0850: 3d 53 3b 20 75 3d 70 72 65 76 5b 75 5d 29 0a 09 =S; u=prev[u])..
0860: 09 09 09 66 20 3d 20 6d 69 6e 28 66 2c 20 46 5b ...f = min(f, F[
0870: 70 72 65 76 5b 75 5d 5d 5b 75 5d 29 3b 0a 09 09 prev[u]][u]);...
0880: 09 52 46 20 20 20 20 20 20 20 20 20 2d 3d 20 66 .RF -= f
0890: 3b 0a 09 09 09 74 6f 74 61 6c 5f 66 6c 6f 77 20 ;....total_flow
08a0: 2b 3d 20 66 3b 0a 0a 09 09 09 66 6f 72 28 69 6e += f;.....for(in
08b0: 74 20 75 3d 54 3b 20 75 21 3d 53 3b 20 75 3d 70 t u=T; u!=S; u=p
08c0: 72 65 76 5b 75 5d 29 0a 09 09 09 7b 0a 09 09 09 rev[u])....{....
08d0: 09 74 6f 74 61 6c 5f 63 6f 73 74 20 20 20 20 2b .total_cost +
08e0: 3d 20 66 20 2a 20 43 5b 70 72 65 76 5b 75 5d 5d = f * C[prev[u]]
08f0: 5b 75 5d 3b 0a 09 09 09 09 46 5b 70 72 65 76 5b [u];.....F[prev[
0900: 75 5d 5d 5b 75 5d 20 2d 3d 20 66 3b 0a 09 09 09 u]][u] -= f;....
0910: 09 46 5b 75 5d 5b 70 72 65 76 5b 75 5d 5d 20 2b .F[u][prev[u]] +
0920: 3d 20 66 3b 0a 09 09 09 7d 0a 0a 09 09 09 2f 2f = f;....}.....//
0930: 20 55 70 64 61 74 65 20 74 68 65 20 70 6f 74 65 Update the pote
0940: 6e 74 69 61 6c 0a 09 09 09 66 6f 72 28 69 6e 74 ntial....for(int
0950: 20 75 3d 30 3b 20 75 3c 4e 3b 20 2b 2b 75 29 0a u=0; u<N; ++u).
0960: 09 09 09 09 68 5b 75 5d 20 2b 3d 20 64 5b 75 5d ....h[u] += d[u]
0970: 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 6d ;...}...return m
0980: 61 6b 65 5f 70 61 69 72 28 74 6f 74 61 6c 5f 63 ake_pair(total_c
0990: 6f 73 74 2c 20 74 6f 74 61 6c 5f 66 6c 6f 77 29 ost, total_flow)
09a0: 3b 0a 09 7d 0a 7d 3b 0a ;..}.};.