Artifact 27b1f3ac721526bcf53951c370bf5b826f25f0f7:
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 53 74 6f 65 72 2d 57 61 67 6e 65 72 .// Stoer-Wagner
0050: 0a 2f 2f 20 4d 69 6e 69 6d 75 6d 20 63 6f 73 74 .// Minimum cost
0060: 20 66 6f 72 20 6d 61 6b 69 6e 67 20 74 68 65 20 for making the
0070: 67 72 61 70 68 20 75 6e 63 6f 6e 6e 65 63 74 65 graph unconnecte
0080: 64 0a 2f 2f 20 20 20 4f 28 56 5e 33 29 0a 2f 2f d.// O(V^3).//
0090: 0a 2f 2f 20 47 20 3a 20 62 69 64 69 72 65 63 74 .// G : bidirect
00a0: 69 6f 6e 61 6c 20 28 47 5b 76 5d 5b 75 5d 20 3d ional (G[v][u] =
00b0: 3d 20 47 5b 75 5d 5b 76 5d 29 0a 2f 2f 0a 2f 2f = G[u][v]).//.//
00c0: 20 56 65 72 69 66 69 65 64 20 62 79 0a 2f 2f 20 Verified by.//
00d0: 20 20 2d 20 53 52 4d 20 33 34 30 20 44 69 76 31 - SRM 340 Div1
00e0: 20 4c 56 33 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d LV3.//---------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0120: 2d 2d 2d 2d 0a 0a 74 79 70 65 64 65 66 20 69 6e ----..typedef in
0130: 74 20 63 6f 73 74 3b 0a 74 79 70 65 64 65 66 20 t cost;.typedef
0140: 69 6e 74 20 76 65 72 74 3b 0a 74 79 70 65 64 65 int vert;.typede
0150: 66 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 f vector< vector
0160: 3c 63 6f 73 74 3e 20 3e 20 67 72 61 70 68 3b 0a <cost> > graph;.
0170: 0a 63 6f 73 74 20 62 69 64 69 5f 6d 69 6e 43 75 .cost bidi_minCu
0180: 74 28 20 67 72 61 70 68 20 47 2c 20 69 6e 74 20 t( graph G, int
0190: 4e 20 29 0a 7b 0a 09 76 65 63 74 6f 72 3c 76 65 N ).{..vector<ve
01a0: 72 74 3e 20 56 3b 0a 09 66 6f 72 28 69 6e 74 20 rt> V;..for(int
01b0: 76 3d 30 3b 20 76 3c 4e 3b 20 2b 2b 76 29 0a 09 v=0; v<N; ++v)..
01c0: 09 56 2e 70 75 73 68 5f 62 61 63 6b 28 76 29 3b .V.push_back(v);
01d0: 0a 0a 09 63 6f 73 74 20 72 65 73 75 6c 74 20 3d ...cost result =
01e0: 20 30 78 37 66 66 66 66 66 66 66 3b 0a 09 66 6f 0x7fffffff;..fo
01f0: 72 28 69 6e 74 20 6e 3d 4e 3b 20 6e 3e 31 3b 20 r(int n=N; n>1;
0200: 2d 2d 6e 29 0a 09 7b 0a 09 09 2f 2f 20 69 6e 76 --n)..{...// inv
0210: 61 72 69 61 6e 74 3a 0a 09 09 2f 2f 20 20 20 74 ariant:...// t
0220: 68 65 20 63 75 72 72 65 6e 74 20 73 65 74 20 6f he current set o
0230: 66 20 76 65 72 74 69 63 65 73 20 3d 20 7b 56 5b f vertices = {V[
0240: 30 5d 20 2e 2e 20 56 5b 6e 2d 31 5d 7d 0a 0a 09 0] .. V[n-1]}...
0250: 09 2f 2f 20 6f 72 64 65 72 20 74 68 65 20 76 65 .// order the ve
0260: 72 74 69 63 65 73 0a 09 09 2f 2f 20 20 20 76 30 rtices...// v0
0270: 20 3d 20 30 20 28 61 72 62 69 74 72 61 72 79 29 = 0 (arbitrary)
0280: 2c 0a 09 09 2f 2f 20 20 20 76 31 20 3d 20 28 75 ,...// v1 = (u
0290: 20 74 68 61 74 20 6d 61 78 69 6d 69 7a 65 73 20 that maximizes
02a0: 5c 53 69 67 6d 61 20 47 5b 76 30 5d 5b 75 5d 29 \Sigma G[v0][u])
02b0: 0a 09 09 2f 2f 20 20 20 76 32 20 3d 20 28 75 20 ...// v2 = (u
02c0: 74 68 61 74 20 6d 61 78 69 6d 69 7a 65 73 20 5c that maximizes \
02d0: 53 69 67 6d 61 20 47 5b 76 30 5d 5b 75 5d 2b 47 Sigma G[v0][u]+G
02e0: 5b 76 31 5d 5b 75 5d 29 0a 09 09 2f 2f 20 20 20 [v1][u])...//
02f0: 2e 2e 2e 0a 09 09 2f 2f 20 20 20 76 6e 2d 32 0a ......// vn-2.
0300: 09 09 2f 2f 20 20 20 76 6e 2d 31 20 3d 20 28 6d ..// vn-1 = (m
0310: 61 78 69 6d 69 7a 65 73 20 6c 61 73 74 43 75 74 aximizes lastCut
0320: 20 3d 20 5c 53 69 67 6d 61 20 47 5b 76 30 5d 5b = \Sigma G[v0][
0330: 75 5d 2b 47 5b 76 6e 2d 32 5d 5b 75 5d 29 0a 09 u]+G[vn-2][u])..
0340: 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 76 73 3b .vector<int> vs;
0350: 0a 09 09 63 6f 73 74 20 6c 61 73 74 43 75 74 20 ...cost lastCut
0360: 3d 20 30 3b 0a 09 09 7b 0a 09 09 09 76 65 63 74 = 0;...{....vect
0370: 6f 72 3c 63 6f 73 74 3e 20 77 73 28 6e 2c 20 30 or<cost> ws(n, 0
0380: 29 3b 0a 09 09 09 77 73 5b 30 5d 20 3d 20 31 3b );....ws[0] = 1;
0390: 0a 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 .....for(int i=0
03a0: 3b 20 69 3c 6e 3b 20 2b 2b 69 29 20 7b 0a 09 09 ; i<n; ++i) {...
03b0: 09 09 69 6e 74 20 6a 20 3d 20 6d 61 78 5f 65 6c ..int j = max_el
03c0: 65 6d 65 6e 74 28 77 73 2e 62 65 67 69 6e 28 29 ement(ws.begin()
03d0: 2c 20 77 73 2e 65 6e 64 28 29 29 20 2d 20 77 73 , ws.end()) - ws
03e0: 2e 62 65 67 69 6e 28 29 3b 0a 09 09 09 09 6c 61 .begin();.....la
03f0: 73 74 43 75 74 20 3d 20 77 73 5b 6a 5d 3b 0a 0a stCut = ws[j];..
0400: 09 09 09 09 76 73 2e 70 75 73 68 5f 62 61 63 6b ....vs.push_back
0410: 28 6a 29 3b 0a 09 09 09 09 77 73 5b 6a 5d 20 3d (j);.....ws[j] =
0420: 20 2d 31 3b 0a 09 09 09 09 66 6f 72 28 69 6e 74 -1;.....for(int
0430: 20 6b 3d 30 3b 20 6b 3c 6e 3b 20 2b 2b 6b 29 0a k=0; k<n; ++k).
0440: 09 09 09 09 09 69 66 28 20 77 73 5b 6b 5d 20 21 .....if( ws[k] !
0450: 3d 20 2d 31 20 29 0a 09 09 09 09 09 09 77 73 5b = -1 ).......ws[
0460: 6b 5d 20 2b 3d 20 47 5b 56 5b 6b 5d 5d 5b 56 5b k] += G[V[k]][V[
0470: 6a 5d 5d 3b 0a 09 09 09 7d 0a 09 09 7d 0a 0a 09 j]];....}...}...
0480: 09 2f 2f 20 75 70 64 61 74 65 20 6d 69 6e 63 75 .// update mincu
0490: 74 0a 09 09 2f 2f 20 20 20 6c 65 6d 6d 61 3a 20 t...// lemma:
04a0: 22 74 68 65 20 6d 69 6e 20 63 6f 73 74 20 66 6f "the min cost fo
04b0: 72 20 73 65 70 61 72 61 74 69 6e 67 20 76 6e 2d r separating vn-
04c0: 32 20 61 6e 64 20 76 6e 2d 31 22 3d 3d 6c 61 73 2 and vn-1"==las
04d0: 74 43 75 74 0a 09 09 72 65 73 75 6c 74 20 3d 20 tCut...result =
04e0: 6d 69 6e 28 72 65 73 75 6c 74 2c 20 6c 61 73 74 min(result, last
04f0: 43 75 74 29 3b 0a 0a 09 09 2f 2f 20 72 65 64 75 Cut);....// redu
0500: 63 65 20 74 68 65 20 67 72 61 70 68 20 28 75 6e ce the graph (un
0510: 69 66 79 20 76 6e 2d 32 20 61 6e 64 20 76 6e 2d ify vn-2 and vn-
0520: 31 29 0a 09 09 2f 2f 20 20 20 66 6f 72 20 74 65 1)...// for te
0530: 73 74 69 6e 67 20 74 68 65 20 63 61 73 65 20 76 sting the case v
0540: 6e 2d 32 20 61 6e 64 20 76 6e 2d 31 20 69 73 20 n-2 and vn-1 is
0550: 63 6f 6e 6e 65 63 74 65 64 0a 09 09 76 65 72 74 connected...vert
0560: 20 76 32 3d 76 73 5b 6e 2d 32 5d 2c 20 76 31 3d v2=vs[n-2], v1=
0570: 76 73 5b 6e 2d 31 5d 3b 0a 09 09 66 6f 72 28 69 vs[n-1];...for(i
0580: 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 2b 2b 69 nt i=0; i<n; ++i
0590: 29 20 7b 0a 09 09 09 47 5b 56 5b 76 32 5d 5d 5b ) {....G[V[v2]][
05a0: 56 5b 69 5d 5d 20 2b 3d 20 47 5b 56 5b 76 31 5d V[i]] += G[V[v1]
05b0: 5d 5b 56 5b 69 5d 5d 3b 0a 09 09 09 47 5b 56 5b ][V[i]];....G[V[
05c0: 69 5d 5d 5b 56 5b 76 32 5d 5d 20 2b 3d 20 47 5b i]][V[v2]] += G[
05d0: 56 5b 69 5d 5d 5b 56 5b 76 31 5d 5d 3b 0a 09 09 V[i]][V[v1]];...
05e0: 7d 0a 09 09 56 2e 65 72 61 73 65 28 20 56 2e 62 }...V.erase( V.b
05f0: 65 67 69 6e 28 29 20 2b 20 76 31 20 29 3b 0a 09 egin() + v1 );..
0600: 7d 0a 09 72 65 74 75 72 6e 20 72 65 73 75 6c 74 }..return result
0610: 3b 0a 7d 0a ;.}.