Artifact 4236b55037662c66a592a8df9920f39f6fd1c653:
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 20 20 20 2d 20 53 52 4d 20 35 32 36 20 44 // - SRM 526 D
00b0: 69 76 31 20 4c 56 31 0a 2f 2f 2d 2d 2d 2d 2d 2d iv1 LV1.//------
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 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 0a 0a 23 69 6e 63 6c 75 64 -------..#includ
0100: 65 20 3c 69 6f 73 74 72 65 61 6d 3e 0a 23 69 6e e <iostream>.#in
0110: 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 3e 0a 23 clude <string>.#
0120: 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e include <vector>
0130: 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 3e 0a .#include <map>.
0140: 23 69 6e 63 6c 75 64 65 20 3c 71 75 65 75 65 3e #include <queue>
0150: 0a 75 73 69 6e 67 20 6e 61 6d 65 73 70 61 63 65 .using namespace
0160: 20 73 74 64 3b 0a 0a 74 65 6d 70 6c 61 74 65 3c std;..template<
0170: 74 79 70 65 6e 61 6d 65 20 54 3e 0a 63 6c 61 73 typename T>.clas
0180: 73 20 49 64 47 65 6e 0a 7b 0a 09 6d 61 70 3c 54 s IdGen.{..map<T
0190: 2c 20 69 6e 74 3e 20 76 32 69 64 5f 3b 0a 09 76 , int> v2id_;..v
01a0: 65 63 74 6f 72 3c 54 3e 20 20 20 69 64 32 76 5f ector<T> id2v_
01b0: 3b 0a 70 75 62 6c 69 63 3a 0a 09 69 6e 74 20 76 ;.public:..int v
01c0: 32 69 64 28 63 6f 6e 73 74 20 54 26 20 76 29 20 2id(const T& v)
01d0: 7b 0a 09 09 69 66 28 20 21 76 32 69 64 5f 2e 63 {...if( !v2id_.c
01e0: 6f 75 6e 74 28 76 29 20 29 20 7b 20 76 32 69 64 ount(v) ) { v2id
01f0: 5f 5b 76 5d 20 3d 20 73 69 7a 65 28 29 3b 20 69 _[v] = size(); i
0200: 64 32 76 5f 2e 70 75 73 68 5f 62 61 63 6b 28 76 d2v_.push_back(v
0210: 29 3b 20 7d 0a 09 09 72 65 74 75 72 6e 20 76 32 ); }...return v2
0220: 69 64 5f 5b 76 5d 3b 0a 09 7d 0a 09 63 6f 6e 73 id_[v];..}..cons
0230: 74 20 54 26 20 69 64 32 76 28 69 6e 74 20 69 29 t T& id2v(int i)
0240: 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 6e 20 const { return
0250: 69 64 32 76 5f 5b 69 5d 3b 20 7d 0a 09 69 6e 74 id2v_[i]; }..int
0260: 20 73 69 7a 65 28 29 20 63 6f 6e 73 74 20 7b 20 size() const {
0270: 72 65 74 75 72 6e 20 69 64 32 76 5f 2e 73 69 7a return id2v_.siz
0280: 65 28 29 3b 20 7d 0a 7d 3b 0a 0a 74 65 6d 70 6c e(); }.};..templ
0290: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 56 65 72 ate<typename Ver
02a0: 74 2c 20 74 79 70 65 6e 61 6d 65 20 43 6f 73 74 t, typename Cost
02b0: 2c 20 74 79 70 65 6e 61 6d 65 20 46 6c 6f 77 2c , typename Flow,
02c0: 20 69 6e 74 20 4e 56 3d 32 35 36 3e 0a 63 6c 61 int NV=256>.cla
02d0: 73 73 20 4d 69 6e 43 6f 73 74 46 6c 6f 77 0a 7b ss MinCostFlow.{
02e0: 0a 09 49 64 47 65 6e 3c 56 65 72 74 3e 20 69 64 ..IdGen<Vert> id
02f0: 67 65 6e 3b 0a 0a 09 76 65 63 74 6f 72 3c 69 6e gen;...vector<in
0300: 74 3e 20 47 5b 4e 56 5d 3b 0a 09 46 6c 6f 77 20 t> G[NV];..Flow
0310: 46 5b 4e 56 5d 5b 4e 56 5d 3b 0a 09 43 6f 73 74 F[NV][NV];..Cost
0320: 20 43 5b 4e 56 5d 5b 4e 56 5d 3b 0a 0a 70 75 62 C[NV][NV];..pub
0330: 6c 69 63 3a 0a 09 76 6f 69 64 20 61 64 64 45 64 lic:..void addEd
0340: 67 65 28 20 56 65 72 74 20 73 5f 2c 20 56 65 72 ge( Vert s_, Ver
0350: 74 20 74 5f 2c 20 43 6f 73 74 20 63 2c 20 46 6c t t_, Cost c, Fl
0360: 6f 77 20 66 20 29 0a 09 7b 0a 09 09 69 6e 74 20 ow f )..{...int
0370: 73 20 3d 20 69 64 67 65 6e 2e 76 32 69 64 28 73 s = idgen.v2id(s
0380: 5f 29 2c 20 74 20 3d 20 69 64 67 65 6e 2e 76 32 _), t = idgen.v2
0390: 69 64 28 74 5f 29 3b 0a 09 09 47 5b 73 5d 2e 70 id(t_);...G[s].p
03a0: 75 73 68 5f 62 61 63 6b 28 74 29 3b 0a 09 09 47 ush_back(t);...G
03b0: 5b 74 5d 2e 70 75 73 68 5f 62 61 63 6b 28 73 29 [t].push_back(s)
03c0: 3b 0a 09 09 43 5b 73 5d 5b 74 5d 20 3d 20 63 3b ;...C[s][t] = c;
03d0: 0a 09 09 43 5b 74 5d 5b 73 5d 20 3d 20 2d 63 3b ...C[t][s] = -c;
03e0: 0a 09 09 46 5b 73 5d 5b 74 5d 20 3d 20 66 3b 0a ...F[s][t] = f;.
03f0: 09 09 46 5b 74 5d 5b 73 5d 20 3d 20 30 3b 0a 09 ..F[t][s] = 0;..
0400: 7d 0a 0a 09 70 61 69 72 3c 43 6f 73 74 2c 20 46 }...pair<Cost, F
0410: 6c 6f 77 3e 20 63 61 6c 63 28 20 56 65 72 74 20 low> calc( Vert
0420: 73 5f 2c 20 56 65 72 74 20 74 5f 20 29 0a 09 7b s_, Vert t_ )..{
0430: 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 4e 3d 69 ...const int N=i
0440: 64 67 65 6e 2e 73 69 7a 65 28 29 2c 20 53 3d 69 dgen.size(), S=i
0450: 64 67 65 6e 2e 76 32 69 64 28 73 5f 29 2c 20 54 dgen.v2id(s_), T
0460: 3d 69 64 67 65 6e 2e 76 32 69 64 28 74 5f 29 3b =idgen.v2id(t_);
0470: 0a 09 09 73 74 61 74 69 63 20 63 6f 6e 73 74 20 ...static const
0480: 43 6f 73 74 20 43 4f 53 54 5f 49 4e 46 20 3d 20 Cost COST_INF =
0490: 2f 2f 20 30 78 37 66 66 66 66 66 66 66 3b 20 2f // 0x7fffffff; /
04a0: 2f 20 21 21 45 44 49 54 20 48 45 52 45 21 21 0a / !!EDIT HERE!!.
04b0: 09 09 73 74 61 74 69 63 20 63 6f 6e 73 74 20 46 ..static const F
04c0: 6c 6f 77 20 46 4c 4f 57 5f 49 4e 46 20 3d 20 2f low FLOW_INF = /
04d0: 2f 20 30 78 37 66 66 66 66 66 66 66 3b 0a 0a 09 / 0x7fffffff;...
04e0: 09 43 6f 73 74 20 74 6f 74 61 6c 5f 63 6f 73 74 .Cost total_cost
04f0: 20 3d 20 30 3b 0a 09 09 46 6c 6f 77 20 74 6f 74 = 0;...Flow tot
0500: 61 6c 5f 66 6c 6f 77 20 3d 20 30 3b 0a 09 09 76 al_flow = 0;...v
0510: 65 63 74 6f 72 3c 43 6f 73 74 3e 20 68 28 4e 2c ector<Cost> h(N,
0520: 20 30 29 3b 20 2f 2f 20 70 6f 74 65 6e 74 69 61 0); // potentia
0530: 6c 0a 09 09 66 6f 72 28 46 6c 6f 77 20 52 46 3d l...for(Flow RF=
0540: 46 4c 4f 57 5f 49 4e 46 3b 20 52 46 3e 30 3b 20 FLOW_INF; RF>0;
0550: 29 20 2f 2f 20 72 65 73 69 64 75 61 6c 20 66 6c ) // residual fl
0560: 6f 77 0a 09 09 7b 0a 09 09 09 2f 2f 20 44 69 6a ow...{....// Dij
0570: 6b 73 74 72 61 20 2d 2d 20 66 69 6e 64 20 74 68 kstra -- find th
0580: 65 20 6d 69 6e 2d 63 6f 73 74 20 70 61 74 68 0a e min-cost path.
0590: 09 09 09 76 65 63 74 6f 72 3c 43 6f 73 74 3e 20 ...vector<Cost>
05a0: 64 28 4e 2c 20 43 4f 53 54 5f 49 4e 46 29 3b 20 d(N, COST_INF);
05b0: 20 64 5b 53 5d 20 3d 20 30 3b 0a 09 09 09 76 65 d[S] = 0;....ve
05c0: 63 74 6f 72 3c 69 6e 74 3e 20 20 70 72 65 76 28 ctor<int> prev(
05d0: 4e 2c 20 2d 31 29 3b 0a 0a 09 09 09 74 79 70 65 N, -1);.....type
05e0: 64 65 66 20 70 61 69 72 3c 20 43 6f 73 74 2c 20 def pair< Cost,
05f0: 70 61 69 72 3c 69 6e 74 2c 69 6e 74 3e 20 3e 20 pair<int,int> >
0600: 63 65 64 67 65 3b 0a 09 09 09 70 72 69 6f 72 69 cedge;....priori
0610: 74 79 5f 71 75 65 75 65 3c 20 63 65 64 67 65 2c ty_queue< cedge,
0620: 20 76 65 63 74 6f 72 3c 63 65 64 67 65 3e 2c 20 vector<cedge>,
0630: 67 72 65 61 74 65 72 3c 63 65 64 67 65 3e 20 3e greater<cedge> >
0640: 20 51 3b 0a 09 09 09 51 2e 70 75 73 68 28 20 63 Q;....Q.push( c
0650: 65 64 67 65 28 30 2c 20 6d 61 6b 65 5f 70 61 69 edge(0, make_pai
0660: 72 28 53 2c 53 29 29 20 29 3b 0a 09 09 09 77 68 r(S,S)) );....wh
0670: 69 6c 65 28 20 21 51 2e 65 6d 70 74 79 28 29 20 ile( !Q.empty()
0680: 29 20 7b 0a 09 09 09 09 63 65 64 67 65 20 65 20 ) {.....cedge e
0690: 3d 20 51 2e 74 6f 70 28 29 3b 20 51 2e 70 6f 70 = Q.top(); Q.pop
06a0: 28 29 3b 0a 09 09 09 09 69 66 28 20 70 72 65 76 ();.....if( prev
06b0: 5b 65 2e 73 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 [e.second.second
06c0: 5d 20 3e 3d 20 30 20 29 0a 09 09 09 09 09 63 6f ] >= 0 )......co
06d0: 6e 74 69 6e 75 65 3b 0a 09 09 09 09 70 72 65 76 ntinue;.....prev
06e0: 5b 65 2e 73 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 [e.second.second
06f0: 5d 20 3d 20 65 2e 73 65 63 6f 6e 64 2e 66 69 72 ] = e.second.fir
0700: 73 74 3b 0a 0a 09 09 09 09 69 6e 74 20 75 20 3d st;......int u =
0710: 20 65 2e 73 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 e.second.second
0720: 3b 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d ;.....for(int i=
0730: 30 3b 20 69 3c 47 5b 75 5d 2e 73 69 7a 65 28 29 0; i<G[u].size()
0740: 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 69 6e ; ++i) {......in
0750: 74 20 20 76 20 3d 20 47 5b 75 5d 5b 69 5d 3b 0a t v = G[u][i];.
0760: 09 09 09 09 09 43 6f 73 74 20 72 5f 63 6f 73 74 .....Cost r_cost
0770: 20 3d 20 43 5b 75 5d 5b 76 5d 20 2b 20 68 5b 75 = C[u][v] + h[u
0780: 5d 20 2d 20 68 5b 76 5d 3b 0a 09 09 09 09 09 69 ] - h[v];......i
0790: 66 28 20 46 5b 75 5d 5b 76 5d 20 3e 20 30 20 26 f( F[u][v] > 0 &
07a0: 26 20 64 5b 76 5d 20 3e 20 64 5b 75 5d 2b 72 5f & d[v] > d[u]+r_
07b0: 63 6f 73 74 20 29 0a 09 09 09 09 09 09 51 2e 70 cost ).......Q.p
07c0: 75 73 68 28 20 63 65 64 67 65 28 64 5b 76 5d 3d ush( cedge(d[v]=
07d0: 64 5b 75 5d 2b 72 5f 63 6f 73 74 2c 20 6d 61 6b d[u]+r_cost, mak
07e0: 65 5f 70 61 69 72 28 75 2c 76 29 29 20 29 3b 0a e_pair(u,v)) );.
07f0: 09 09 09 09 7d 0a 09 09 09 7d 0a 0a 09 09 09 69 ....}....}.....i
0800: 66 28 20 70 72 65 76 5b 54 5d 20 3c 20 30 20 29 f( prev[T] < 0 )
0810: 0a 09 09 09 09 62 72 65 61 6b 3b 20 2f 2f 20 46 .....break; // F
0820: 69 6e 69 73 68 65 64 0a 0a 09 09 09 2f 2f 20 52 inished.....// R
0830: 75 6e 20 74 68 65 20 66 6c 6f 77 20 61 73 20 6d un the flow as m
0840: 75 63 68 20 61 73 20 70 6f 73 73 69 62 6c 65 0a uch as possible.
0850: 09 09 09 46 6c 6f 77 20 66 20 3d 20 52 46 3b 0a ...Flow f = RF;.
0860: 09 09 09 66 6f 72 28 69 6e 74 20 75 3d 54 3b 20 ...for(int u=T;
0870: 75 21 3d 53 3b 20 75 3d 70 72 65 76 5b 75 5d 29 u!=S; u=prev[u])
0880: 0a 09 09 09 09 66 20 3d 20 6d 69 6e 28 66 2c 20 .....f = min(f,
0890: 46 5b 70 72 65 76 5b 75 5d 5d 5b 75 5d 29 3b 0a F[prev[u]][u]);.
08a0: 09 09 09 52 46 20 20 20 20 20 20 20 20 20 2d 3d ...RF -=
08b0: 20 66 3b 0a 09 09 09 74 6f 74 61 6c 5f 66 6c 6f f;....total_flo
08c0: 77 20 2b 3d 20 66 3b 0a 0a 09 09 09 66 6f 72 28 w += f;.....for(
08d0: 69 6e 74 20 75 3d 54 3b 20 75 21 3d 53 3b 20 75 int u=T; u!=S; u
08e0: 3d 70 72 65 76 5b 75 5d 29 0a 09 09 09 7b 0a 09 =prev[u])....{..
08f0: 09 09 09 74 6f 74 61 6c 5f 63 6f 73 74 20 20 20 ...total_cost
0900: 20 2b 3d 20 66 20 2a 20 43 5b 70 72 65 76 5b 75 += f * C[prev[u
0910: 5d 5d 5b 75 5d 3b 0a 09 09 09 09 46 5b 70 72 65 ]][u];.....F[pre
0920: 76 5b 75 5d 5d 5b 75 5d 20 2d 3d 20 66 3b 0a 09 v[u]][u] -= f;..
0930: 09 09 09 46 5b 75 5d 5b 70 72 65 76 5b 75 5d 5d ...F[u][prev[u]]
0940: 20 2b 3d 20 66 3b 0a 09 09 09 7d 0a 0a 09 09 09 += f;....}.....
0950: 2f 2f 20 55 70 64 61 74 65 20 74 68 65 20 70 6f // Update the po
0960: 74 65 6e 74 69 61 6c 0a 09 09 09 66 6f 72 28 69 tential....for(i
0970: 6e 74 20 75 3d 30 3b 20 75 3c 4e 3b 20 2b 2b 75 nt u=0; u<N; ++u
0980: 29 0a 09 09 09 09 68 5b 75 5d 20 2b 3d 20 64 5b ).....h[u] += d[
0990: 75 5d 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e u];...}...return
09a0: 20 6d 61 6b 65 5f 70 61 69 72 28 74 6f 74 61 6c make_pair(total
09b0: 5f 63 6f 73 74 2c 20 74 6f 74 61 6c 5f 66 6c 6f _cost, total_flo
09c0: 77 29 3b 0a 09 7d 0a 7d 3b 0a w);..}.};.