Artifact f4ac9260460b22415cfc0d2e04f344e1ca445fc2:
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 46 20 45 20 6c 6f ow.// O(F E lo
0060: 67 20 45 29 20 20 20 20 2f 2f 20 46 3a 66 6c 6f g E) // F:flo
0070: 77 0a 2f 2f 20 20 20 53 65 65 20 68 74 74 70 3a w.// See http:
0080: 2f 2f 64 2e 68 61 74 65 6e 61 2e 6e 65 2e 6a 70 //d.hatena.ne.jp
0090: 2f 74 73 75 6b 75 6e 6f 2f 32 30 31 32 30 33 32 /tsukuno/2012032
00a0: 30 23 31 33 33 32 31 37 39 31 34 33 0a 2f 2f 0a 0#1332179143.//.
00b0: 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 0a 2f // Verified by./
00c0: 2f 20 20 20 2d 20 28 53 52 4d 20 34 38 37 20 44 / - (SRM 487 D
00d0: 69 76 32 20 4c 56 33 29 20 69 6e 20 70 72 65 76 iv2 LV3) in prev
00e0: 69 6f 75 73 20 76 65 72 73 69 6f 6e 0a 2f 2f 20 ious version.//
00f0: 20 20 2d 20 28 53 52 4d 20 35 32 36 20 44 69 76 - (SRM 526 Div
0100: 31 20 4c 56 31 29 20 69 6e 20 70 72 65 76 69 6f 1 LV1) in previo
0110: 75 73 20 76 65 72 73 69 6f 6e 0a 2f 2f 20 20 20 us version.//
0120: 2d 20 53 52 4d 20 34 39 31 20 44 69 76 31 20 4c - SRM 491 Div1 L
0130: 56 33 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d V3.//-----------
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 0a 0a 23 69 6e 63 6c 75 64 65 20 3c 69 6f --..#include <io
0180: 73 74 72 65 61 6d 3e 0a 23 69 6e 63 6c 75 64 65 stream>.#include
0190: 20 3c 73 74 72 69 6e 67 3e 0a 23 69 6e 63 6c 75 <string>.#inclu
01a0: 64 65 20 3c 76 65 63 74 6f 72 3e 0a 23 69 6e 63 de <vector>.#inc
01b0: 6c 75 64 65 20 3c 6d 61 70 3e 0a 23 69 6e 63 6c lude <map>.#incl
01c0: 75 64 65 20 3c 71 75 65 75 65 3e 0a 75 73 69 6e ude <queue>.usin
01d0: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
01e0: 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e ..template<typen
01f0: 61 6d 65 20 54 3e 0a 63 6c 61 73 73 20 49 64 47 ame T>.class IdG
0200: 65 6e 0a 7b 0a 09 6d 61 70 3c 54 2c 20 69 6e 74 en.{..map<T, int
0210: 3e 20 76 32 69 64 5f 3b 0a 09 76 65 63 74 6f 72 > v2id_;..vector
0220: 3c 54 3e 20 20 20 69 64 32 76 5f 3b 0a 70 75 62 <T> id2v_;.pub
0230: 6c 69 63 3a 0a 09 69 6e 74 20 76 32 69 64 28 63 lic:..int v2id(c
0240: 6f 6e 73 74 20 54 26 20 76 29 20 7b 0a 09 09 69 onst T& v) {...i
0250: 66 28 20 21 76 32 69 64 5f 2e 63 6f 75 6e 74 28 f( !v2id_.count(
0260: 76 29 20 29 20 7b 20 76 32 69 64 5f 5b 76 5d 20 v) ) { v2id_[v]
0270: 3d 20 73 69 7a 65 28 29 3b 20 69 64 32 76 5f 2e = size(); id2v_.
0280: 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 7d 0a push_back(v); }.
0290: 09 09 72 65 74 75 72 6e 20 76 32 69 64 5f 5b 76 ..return v2id_[v
02a0: 5d 3b 0a 09 7d 0a 09 63 6f 6e 73 74 20 54 26 20 ];..}..const T&
02b0: 69 64 32 76 28 69 6e 74 20 69 29 20 63 6f 6e 73 id2v(int i) cons
02c0: 74 20 7b 20 72 65 74 75 72 6e 20 69 64 32 76 5f t { return id2v_
02d0: 5b 69 5d 3b 20 7d 0a 09 69 6e 74 20 73 69 7a 65 [i]; }..int size
02e0: 28 29 20 63 6f 6e 73 74 20 7b 20 72 65 74 75 72 () const { retur
02f0: 6e 20 69 64 32 76 5f 2e 73 69 7a 65 28 29 3b 20 n id2v_.size();
0300: 7d 0a 7d 3b 0a 0a 74 65 6d 70 6c 61 74 65 3c 74 }.};..template<t
0310: 79 70 65 6e 61 6d 65 20 56 65 72 74 2c 20 74 79 ypename Vert, ty
0320: 70 65 6e 61 6d 65 20 43 6f 73 74 2c 20 74 79 70 pename Cost, typ
0330: 65 6e 61 6d 65 20 46 6c 6f 77 2c 20 69 6e 74 20 ename Flow, int
0340: 4e 56 3d 32 35 36 3e 0a 63 6c 61 73 73 20 4d 69 NV=256>.class Mi
0350: 6e 43 6f 73 74 46 6c 6f 77 0a 7b 0a 09 49 64 47 nCostFlow.{..IdG
0360: 65 6e 3c 56 65 72 74 3e 20 69 64 67 65 6e 3b 0a en<Vert> idgen;.
0370: 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 47 5b ..vector<int> G[
0380: 4e 56 5d 3b 0a 09 46 6c 6f 77 20 46 5b 4e 56 5d NV];..Flow F[NV]
0390: 5b 4e 56 5d 3b 0a 09 43 6f 73 74 20 43 5b 4e 56 [NV];..Cost C[NV
03a0: 5d 5b 4e 56 5d 3b 0a 0a 70 75 62 6c 69 63 3a 0a ][NV];..public:.
03b0: 09 76 6f 69 64 20 61 64 64 45 64 67 65 28 20 56 .void addEdge( V
03c0: 65 72 74 20 73 5f 2c 20 56 65 72 74 20 74 5f 2c ert s_, Vert t_,
03d0: 20 43 6f 73 74 20 63 2c 20 46 6c 6f 77 20 66 20 Cost c, Flow f
03e0: 29 0a 09 7b 0a 09 09 69 6e 74 20 73 20 3d 20 69 )..{...int s = i
03f0: 64 67 65 6e 2e 76 32 69 64 28 73 5f 29 2c 20 74 dgen.v2id(s_), t
0400: 20 3d 20 69 64 67 65 6e 2e 76 32 69 64 28 74 5f = idgen.v2id(t_
0410: 29 3b 0a 09 09 47 5b 73 5d 2e 70 75 73 68 5f 62 );...G[s].push_b
0420: 61 63 6b 28 74 29 3b 0a 09 09 47 5b 74 5d 2e 70 ack(t);...G[t].p
0430: 75 73 68 5f 62 61 63 6b 28 73 29 3b 0a 09 09 43 ush_back(s);...C
0440: 5b 73 5d 5b 74 5d 20 3d 20 63 3b 0a 09 09 43 5b [s][t] = c;...C[
0450: 74 5d 5b 73 5d 20 3d 20 2d 63 3b 0a 09 09 46 5b t][s] = -c;...F[
0460: 73 5d 5b 74 5d 20 3d 20 66 3b 0a 09 09 46 5b 74 s][t] = f;...F[t
0470: 5d 5b 73 5d 20 3d 20 30 3b 0a 09 7d 0a 0a 09 70 ][s] = 0;..}...p
0480: 61 69 72 3c 43 6f 73 74 2c 20 46 6c 6f 77 3e 20 air<Cost, Flow>
0490: 63 61 6c 63 28 20 56 65 72 74 20 73 5f 2c 20 56 calc( Vert s_, V
04a0: 65 72 74 20 74 5f 20 29 0a 09 7b 0a 09 09 63 6f ert t_ )..{...co
04b0: 6e 73 74 20 69 6e 74 20 4e 3d 69 64 67 65 6e 2e nst int N=idgen.
04c0: 73 69 7a 65 28 29 2c 20 53 3d 69 64 67 65 6e 2e size(), S=idgen.
04d0: 76 32 69 64 28 73 5f 29 2c 20 54 3d 69 64 67 65 v2id(s_), T=idge
04e0: 6e 2e 76 32 69 64 28 74 5f 29 3b 0a 09 09 73 74 n.v2id(t_);...st
04f0: 61 74 69 63 20 63 6f 6e 73 74 20 43 6f 73 74 20 atic const Cost
0500: 43 4f 53 54 5f 49 4e 46 20 3d 20 31 65 2b 33 30 COST_INF = 1e+30
0510: 30 3b 20 2f 2f 20 21 21 45 44 49 54 20 48 45 52 0; // !!EDIT HER
0520: 45 21 21 0a 09 09 73 74 61 74 69 63 20 63 6f 6e E!!...static con
0530: 73 74 20 46 6c 6f 77 20 46 4c 4f 57 5f 49 4e 46 st Flow FLOW_INF
0540: 20 3d 20 30 78 37 66 66 66 66 66 66 66 3b 0a 0a = 0x7fffffff;..
0550: 09 09 43 6f 73 74 20 74 6f 74 61 6c 5f 63 6f 73 ..Cost total_cos
0560: 74 20 3d 20 30 3b 0a 09 09 46 6c 6f 77 20 74 6f t = 0;...Flow to
0570: 74 61 6c 5f 66 6c 6f 77 20 3d 20 30 3b 0a 09 09 tal_flow = 0;...
0580: 76 65 63 74 6f 72 3c 43 6f 73 74 3e 20 64 69 73 vector<Cost> dis
0590: 74 28 4e 2c 20 30 29 3b 20 2f 2f 20 44 69 73 74 t(N, 0); // Dist
05a0: 61 6e 63 65 20 66 72 6f 6d 20 53 20 3a 20 69 6e ance from S : in
05b0: 69 74 69 61 6c 6c 79 20 75 6e 6b 6e 6f 77 6e 2e itially unknown.
05c0: 0a 09 09 66 6f 72 28 3b 3b 29 0a 09 09 7b 0a 09 ...for(;;)...{..
05d0: 09 09 2f 2f 20 44 69 6a 6b 73 74 72 61 20 3a 20 ..// Dijkstra :
05e0: 66 69 6e 64 20 74 68 65 20 22 73 68 6f 72 74 65 find the "shorte
05f0: 73 74 20 70 61 74 68 22 20 66 72 6f 6d 20 53 20 st path" from S
0600: 74 6f 20 54 20 77 72 74 20 43 5b 5d 5b 5d 2e 0a to T wrt C[][]..
0610: 09 09 09 2f 2f 20 20 20 43 5b 5d 5b 5d 20 63 61 ...// C[][] ca
0620: 6e 20 62 65 20 3c 30 20 73 6f 20 77 65 20 6d 75 n be <0 so we mu
0630: 73 74 20 62 65 20 63 61 72 65 66 75 6c 2e 20 49 st be careful. I
0640: 6e 73 74 65 61 64 20 6f 66 20 63 6f 6d 70 75 74 nstead of comput
0650: 69 6e 67 20 74 68 65 20 73 68 6f 72 74 65 73 74 ing the shortest
0660: 20 70 61 74 68 20 64 69 72 65 63 74 6c 79 2c 0a path directly,.
0670: 09 09 09 2f 2f 20 20 20 77 65 20 63 6f 6d 70 75 ...// we compu
0680: 74 65 20 74 68 65 20 69 6e 63 72 65 61 73 65 20 te the increase
0690: 28 22 64 65 6c 74 61 22 29 20 66 72 6f 6d 20 74 ("delta") from t
06a0: 68 65 20 73 68 6f 72 74 65 73 74 20 70 61 74 68 he shortest path
06b0: 20 69 6e 20 74 68 65 20 70 72 65 76 69 6f 75 73 in the previous
06c0: 20 69 74 65 72 61 74 69 6f 6e 2e 0a 09 09 09 2f iteration...../
06d0: 2f 20 20 20 53 69 6e 63 65 20 73 68 6f 72 74 65 / Since shorte
06e0: 73 74 20 70 61 74 68 20 63 61 6e 6e 6f 74 20 64 st path cannot d
06f0: 65 63 72 65 61 73 65 2c 20 64 65 6c 74 61 20 69 ecrease, delta i
0700: 73 20 61 6c 77 61 79 73 20 3e 3d 30 20 77 68 65 s always >=0 whe
0710: 6e 20 74 72 61 76 65 72 73 69 6e 67 20 65 64 67 n traversing edg
0720: 65 73 2e 0a 09 09 09 2f 2f 20 20 20 53 6d 61 6c es.....// Smal
0730: 6c 65 73 74 20 64 65 6c 74 61 20 69 6d 70 6c 69 lest delta impli
0740: 65 73 20 73 6d 61 6c 6c 65 73 74 20 64 69 73 74 es smallest dist
0750: 5b 54 5d 2b 64 65 6c 74 61 5b 54 5d 2e 0a 09 09 [T]+delta[T]....
0760: 09 76 65 63 74 6f 72 3c 43 6f 73 74 3e 20 64 65 .vector<Cost> de
0770: 6c 74 61 28 4e 2c 20 43 4f 53 54 5f 49 4e 46 29 lta(N, COST_INF)
0780: 3b 20 64 65 6c 74 61 5b 53 5d 20 3d 20 30 3b 0a ; delta[S] = 0;.
0790: 09 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 20 ...vector<int>
07a0: 70 72 65 76 28 4e 2c 20 2d 31 29 3b 0a 0a 09 09 prev(N, -1);....
07b0: 09 74 79 70 65 64 65 66 20 70 61 69 72 3c 20 43 .typedef pair< C
07c0: 6f 73 74 2c 20 70 61 69 72 3c 69 6e 74 2c 20 69 ost, pair<int, i
07d0: 6e 74 3e 20 3e 20 63 65 64 67 65 3b 0a 09 09 09 nt> > cedge;....
07e0: 70 72 69 6f 72 69 74 79 5f 71 75 65 75 65 3c 20 priority_queue<
07f0: 63 65 64 67 65 2c 20 76 65 63 74 6f 72 3c 63 65 cedge, vector<ce
0800: 64 67 65 3e 2c 20 67 72 65 61 74 65 72 3c 63 65 dge>, greater<ce
0810: 64 67 65 3e 20 3e 20 51 3b 0a 09 09 09 51 2e 70 dge> > Q;....Q.p
0820: 75 73 68 28 20 63 65 64 67 65 28 30 2c 20 6d 61 ush( cedge(0, ma
0830: 6b 65 5f 70 61 69 72 28 53 2c 20 53 29 29 20 29 ke_pair(S, S)) )
0840: 3b 0a 09 09 09 77 68 69 6c 65 28 20 21 51 2e 65 ;....while( !Q.e
0850: 6d 70 74 79 28 29 20 29 20 7b 0a 09 09 09 09 63 mpty() ) {.....c
0860: 6f 6e 73 74 20 63 65 64 67 65 20 65 20 3d 20 51 onst cedge e = Q
0870: 2e 74 6f 70 28 29 3b 20 51 2e 70 6f 70 28 29 3b .top(); Q.pop();
0880: 0a 09 09 09 09 63 6f 6e 73 74 20 69 6e 74 20 75 .....const int u
0890: 5f 70 72 65 76 20 3d 20 65 2e 73 65 63 6f 6e 64 _prev = e.second
08a0: 2e 66 69 72 73 74 3b 0a 09 09 09 09 63 6f 6e 73 .first;.....cons
08b0: 74 20 69 6e 74 20 75 20 3d 20 65 2e 73 65 63 6f t int u = e.seco
08c0: 6e 64 2e 73 65 63 6f 6e 64 3b 0a 09 09 09 09 69 nd.second;.....i
08d0: 66 28 20 70 72 65 76 5b 75 5d 20 3e 3d 20 30 20 f( prev[u] >= 0
08e0: 29 20 2f 2f 20 76 69 73 69 74 65 64 0a 09 09 09 ) // visited....
08f0: 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 09 09 ..continue;.....
0900: 70 72 65 76 5b 75 5d 20 3d 20 75 5f 70 72 65 76 prev[u] = u_prev
0910: 3b 0a 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 69 ;......for(int i
0920: 3d 30 3b 20 69 3c 47 5b 75 5d 2e 73 69 7a 65 28 =0; i<G[u].size(
0930: 29 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 09 63 ); ++i) {......c
0940: 6f 6e 73 74 20 69 6e 74 20 20 76 20 3d 20 47 5b onst int v = G[
0950: 75 5d 5b 69 5d 3b 0a 09 09 09 09 09 63 6f 6e 73 u][i];......cons
0960: 74 20 43 6f 73 74 20 76 5f 64 65 6c 74 61 20 3d t Cost v_delta =
0970: 20 64 69 73 74 5b 75 5d 2b 64 65 6c 74 61 5b 75 dist[u]+delta[u
0980: 5d 2b 43 5b 75 5d 5b 76 5d 20 2d 20 64 69 73 74 ]+C[u][v] - dist
0990: 5b 76 5d 3b 0a 09 09 09 09 09 69 66 28 20 46 5b [v];......if( F[
09a0: 75 5d 5b 76 5d 3e 30 20 26 26 20 64 65 6c 74 61 u][v]>0 && delta
09b0: 5b 76 5d 3e 76 5f 64 65 6c 74 61 20 29 0a 09 09 [v]>v_delta )...
09c0: 09 09 09 09 51 2e 70 75 73 68 28 20 63 65 64 67 ....Q.push( cedg
09d0: 65 28 64 65 6c 74 61 5b 76 5d 3d 76 5f 64 65 6c e(delta[v]=v_del
09e0: 74 61 2c 20 6d 61 6b 65 5f 70 61 69 72 28 75 2c ta, make_pair(u,
09f0: 76 29 29 20 29 3b 0a 09 09 09 09 7d 0a 09 09 09 v)) );.....}....
0a00: 7d 0a 0a 09 09 09 2f 2f 20 49 66 20 54 20 69 73 }.....// If T is
0a10: 20 75 6e 72 65 61 63 68 61 62 6c 65 2c 20 66 69 unreachable, fi
0a20: 6e 69 73 68 65 64 2e 0a 09 09 09 69 66 28 20 70 nished.....if( p
0a30: 72 65 76 5b 54 5d 20 3c 20 30 20 29 0a 09 09 09 rev[T] < 0 )....
0a40: 09 62 72 65 61 6b 3b 0a 0a 09 09 09 2f 2f 20 55 .break;.....// U
0a50: 70 64 61 74 65 20 74 68 65 20 64 69 73 74 61 6e pdate the distan
0a60: 63 65 20 74 61 62 6c 65 2e 0a 09 09 09 66 6f 72 ce table.....for
0a70: 28 69 6e 74 20 75 3d 30 3b 20 75 3c 4e 3b 20 2b (int u=0; u<N; +
0a80: 2b 75 29 0a 09 09 09 09 69 66 28 20 64 65 6c 74 +u).....if( delt
0a90: 61 5b 75 5d 20 21 3d 20 43 4f 53 54 5f 49 4e 46 a[u] != COST_INF
0aa0: 20 29 0a 09 09 09 09 09 64 69 73 74 5b 75 5d 20 )......dist[u]
0ab0: 2b 3d 20 64 65 6c 74 61 5b 75 5d 3b 0a 0a 09 09 += delta[u];....
0ac0: 09 2f 2f 20 48 6f 77 20 6d 75 63 68 20 77 61 74 .// How much wat
0ad0: 65 72 20 63 61 6e 20 66 6c 6f 77 20 6f 6e 20 74 er can flow on t
0ae0: 68 65 20 6d 69 6e 2d 63 6f 73 74 20 70 61 74 68 he min-cost path
0af0: 3f 0a 09 09 09 46 6c 6f 77 20 66 20 3d 20 46 4c ?....Flow f = FL
0b00: 4f 57 5f 49 4e 46 3b 0a 09 09 09 66 6f 72 28 69 OW_INF;....for(i
0b10: 6e 74 20 75 3d 54 3b 20 75 21 3d 53 3b 20 75 3d nt u=T; u!=S; u=
0b20: 70 72 65 76 5b 75 5d 29 0a 09 09 09 09 66 20 3d prev[u]).....f =
0b30: 20 6d 69 6e 28 66 2c 20 46 5b 70 72 65 76 5b 75 min(f, F[prev[u
0b40: 5d 5d 5b 75 5d 29 3b 0a 0a 09 09 09 2f 2f 20 52 ]][u]);.....// R
0b50: 75 6e 20 74 68 65 20 66 6c 6f 77 20 61 73 20 6d un the flow as m
0b60: 75 63 68 20 61 73 20 70 6f 73 73 69 62 6c 65 0a uch as possible.
0b70: 09 09 09 74 6f 74 61 6c 5f 66 6c 6f 77 20 2b 3d ...total_flow +=
0b80: 20 66 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 75 f;....for(int u
0b90: 3d 54 3b 20 75 21 3d 53 3b 20 75 3d 70 72 65 76 =T; u!=S; u=prev
0ba0: 5b 75 5d 29 20 7b 0a 09 09 09 09 74 6f 74 61 6c [u]) {.....total
0bb0: 5f 63 6f 73 74 20 20 20 20 2b 3d 20 66 20 2a 20 _cost += f *
0bc0: 43 5b 70 72 65 76 5b 75 5d 5d 5b 75 5d 3b 0a 09 C[prev[u]][u];..
0bd0: 09 09 09 46 5b 70 72 65 76 5b 75 5d 5d 5b 75 5d ...F[prev[u]][u]
0be0: 20 2d 3d 20 66 3b 0a 09 09 09 09 46 5b 75 5d 5b -= f;.....F[u][
0bf0: 70 72 65 76 5b 75 5d 5d 20 2b 3d 20 66 3b 0a 09 prev[u]] += f;..
0c00: 09 09 7d 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e ..}...}...return
0c10: 20 6d 61 6b 65 5f 70 61 69 72 28 74 6f 74 61 6c make_pair(total
0c20: 5f 63 6f 73 74 2c 20 74 6f 74 61 6c 5f 66 6c 6f _cost, total_flo
0c30: 77 29 3b 0a 09 7d 0a 7d 3b 0a w);..}.};.