Artifact 08ac17a6157e8d09cf98835de13eeb57fe4bf28b:
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 47 6f 6d 6f 72 79 2d 48 75 0a 2f 2f .// Gomory-Hu.//
0050: 20 41 6c 6c 20 50 61 69 72 20 4d 69 6e 69 6d 75 All Pair Minimu
0060: 6d 20 43 75 74 73 20 66 6f 72 20 61 6e 20 55 6e m Cuts for an Un
0070: 64 69 72 65 63 74 65 64 20 47 72 61 70 68 0a 2f directed Graph./
0080: 2f 20 20 20 4f 28 56 5e 34 29 0a 2f 2f 0a 2f 2f / O(V^4).//.//
0090: 20 47 20 3a 20 75 6e 64 69 72 65 63 74 65 64 20 G : undirected
00a0: 28 47 5b 69 5d 2e 68 61 73 28 6a 29 20 3c 3d 3d (G[i].has(j) <==
00b0: 3e 20 47 5b 6a 5d 2e 68 61 73 28 69 29 29 0a 2f > G[j].has(i))./
00c0: 2f 20 46 20 3a 20 66 6c 6f 77 2d 63 61 70 61 63 / F : flow-capac
00d0: 69 74 79 20 46 5b 69 5d 5b 6a 5d 20 3d 20 46 5b ity F[i][j] = F[
00e0: 6a 5d 5b 69 5d 20 3d 20 43 61 70 61 63 69 74 79 j][i] = Capacity
00f0: 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 .//.// Verified
0100: 62 79 0a 2f 2f 20 20 20 2d 20 43 6f 64 65 43 72 by.// - CodeCr
0110: 61 66 74 20 30 39 20 43 55 54 53 0a 2f 2f 2d 2d aft 09 CUTS.//--
0120: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
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 0a 0a 73 74 61 -----------..sta
0160: 74 69 63 20 63 6f 6e 73 74 20 69 6e 74 20 4e 56 tic const int NV
0170: 20 3d 20 35 31 32 3b 0a 74 79 70 65 64 65 66 20 = 512;.typedef
0180: 69 6e 74 20 20 20 20 20 20 20 20 20 20 20 66 6c int fl
0190: 6f 77 3b 0a 74 79 70 65 64 65 66 20 69 6e 74 20 ow;.typedef int
01a0: 20 20 20 20 20 20 20 20 20 20 76 65 72 74 3b 0a vert;.
01b0: 74 79 70 65 64 65 66 20 76 65 72 74 20 20 20 20 typedef vert
01c0: 20 20 20 20 20 20 65 64 67 65 3b 0a 74 79 70 65 edge;.type
01d0: 64 65 66 20 76 65 63 74 6f 72 3c 65 64 67 65 3e def vector<edge>
01e0: 20 20 65 64 67 65 73 3b 0a 74 79 70 65 64 65 66 edges;.typedef
01f0: 20 76 65 63 74 6f 72 3c 65 64 67 65 73 3e 20 67 vector<edges> g
0200: 72 61 70 68 3b 0a 74 79 70 65 64 65 66 20 66 6c raph;.typedef fl
0210: 6f 77 20 20 20 20 20 20 20 20 20 20 66 6c 6f 77 ow flow
0220: 5f 67 72 61 70 68 5b 4e 56 5d 5b 4e 56 5d 3b 0a _graph[NV][NV];.
0230: 0a 66 6c 6f 77 5f 67 72 61 70 68 20 47 48 46 3b .flow_graph GHF;
0240: 0a 76 6f 69 64 20 47 6f 6d 6f 72 79 48 75 28 20 .void GomoryHu(
0250: 67 72 61 70 68 26 20 47 2c 20 66 6c 6f 77 5f 67 graph& G, flow_g
0260: 72 61 70 68 20 46 2c 20 66 6c 6f 77 5f 67 72 61 raph F, flow_gra
0270: 70 68 20 41 6c 6c 50 61 69 72 4d 69 6e 43 75 74 ph AllPairMinCut
0280: 20 29 0a 7b 0a 09 69 6e 74 20 4e 20 3d 20 47 2e ).{..int N = G.
0290: 73 69 7a 65 28 29 3b 0a 09 76 65 63 74 6f 72 3c size();..vector<
02a0: 76 65 72 74 3e 20 70 61 72 65 6e 74 28 4e 2c 20 vert> parent(N,
02b0: 30 29 3b 0a 09 76 65 63 74 6f 72 3c 66 6c 6f 77 0);..vector<flow
02c0: 3e 20 77 65 69 67 68 74 28 4e 2c 20 30 29 3b 0a > weight(N, 0);.
02d0: 0a 09 2f 2f 20 63 6f 6e 73 74 72 75 63 74 20 74 ..// construct t
02e0: 68 65 20 47 6f 6d 6f 72 79 2d 48 75 20 54 72 65 he Gomory-Hu Tre
02f0: 65 0a 09 66 6f 72 28 76 65 72 74 20 73 3d 31 3b e..for(vert s=1;
0300: 20 73 3c 4e 3b 20 2b 2b 73 29 0a 09 7b 0a 09 09 s<N; ++s)..{...
0310: 76 65 72 74 20 74 20 3d 20 70 61 72 65 6e 74 5b vert t = parent[
0320: 73 5d 3b 0a 0a 09 09 2f 2f 20 6d 69 6e 63 75 74 s];....// mincut
0330: 20 62 65 74 77 65 65 6e 20 73 20 61 6e 64 20 74 between s and t
0340: 0a 09 09 6d 65 6d 63 70 79 28 47 48 46 2c 20 46 ...memcpy(GHF, F
0350: 2c 20 73 69 7a 65 6f 66 28 47 48 46 29 29 3b 0a , sizeof(GHF));.
0360: 09 09 66 6c 6f 77 20 6d 69 6e 63 75 74 20 3d 20 ..flow mincut =
0370: 30 3b 0a 09 09 66 6f 72 28 3b 3b 29 20 7b 0a 09 0;...for(;;) {..
0380: 09 09 2f 2f 20 62 66 73 0a 09 09 09 76 65 63 74 ..// bfs....vect
0390: 6f 72 3c 76 65 72 74 3e 20 70 72 65 76 28 4e 2c or<vert> prev(N,
03a0: 20 2d 31 29 3b 20 70 72 65 76 5b 73 5d 3d 73 3b -1); prev[s]=s;
03b0: 0a 09 09 09 71 75 65 75 65 3c 76 65 72 74 3e 20 ....queue<vert>
03c0: 51 3b 20 51 2e 70 75 73 68 28 73 29 3b 0a 09 09 Q; Q.push(s);...
03d0: 09 77 68 69 6c 65 28 20 21 51 2e 65 6d 70 74 79 .while( !Q.empty
03e0: 28 29 20 29 20 7b 0a 09 09 09 09 76 65 72 74 20 () ) {.....vert
03f0: 76 20 3d 20 51 2e 66 72 6f 6e 74 28 29 3b 20 51 v = Q.front(); Q
0400: 2e 70 6f 70 28 29 3b 0a 09 09 09 09 66 6f 72 28 .pop();.....for(
0410: 69 6e 74 20 69 3d 30 3b 20 69 3c 47 5b 76 5d 2e int i=0; i<G[v].
0420: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0a 09 size(); ++i) {..
0430: 09 09 09 09 76 65 72 74 20 75 20 3d 20 47 5b 76 ....vert u = G[v
0440: 5d 5b 69 5d 3b 0a 09 09 09 09 09 69 66 28 20 70 ][i];......if( p
0450: 72 65 76 5b 75 5d 3d 3d 2d 31 20 26 26 20 47 48 rev[u]==-1 && GH
0460: 46 5b 76 5d 5b 75 5d 20 29 0a 09 09 09 09 09 09 F[v][u] ).......
0470: 70 72 65 76 5b 75 5d 3d 76 2c 20 51 2e 70 75 73 prev[u]=v, Q.pus
0480: 68 28 75 29 3b 0a 09 09 09 09 7d 0a 09 09 09 7d h(u);.....}....}
0490: 0a 0a 09 09 09 69 66 28 20 70 72 65 76 5b 74 5d .....if( prev[t]
04a0: 20 3d 3d 20 2d 31 20 29 0a 09 09 09 7b 0a 09 09 == -1 )....{...
04b0: 09 09 2f 2f 20 64 6f 6e 65 3a 20 73 65 70 61 72 ..// done: separ
04c0: 65 74 65 64 20 74 6f 20 7b 76 7c 70 72 65 76 5b eted to {v|prev[
04d0: 76 5d 21 3d 2d 31 7d 20 61 6e 64 20 7b 76 7c 70 v]!=-1} and {v|p
04e0: 72 65 76 5b 76 5d 3d 3d 2d 31 7d 0a 09 09 09 09 rev[v]==-1}.....
04f0: 2f 2f 20 73 70 6c 69 74 20 74 27 73 20 63 68 69 // split t's chi
0500: 6c 64 72 65 6e 0a 09 09 09 09 77 65 69 67 68 74 ldren.....weight
0510: 5b 73 5d 20 3d 20 6d 69 6e 63 75 74 3b 0a 09 09 [s] = mincut;...
0520: 09 09 66 6f 72 28 76 65 72 74 20 76 3d 30 3b 20 ..for(vert v=0;
0530: 76 3c 4e 3b 20 2b 2b 76 29 0a 09 09 09 09 09 69 v<N; ++v)......i
0540: 66 28 20 70 61 72 65 6e 74 5b 76 5d 3d 3d 74 20 f( parent[v]==t
0550: 26 26 20 70 72 65 76 5b 76 5d 21 3d 2d 31 20 26 && prev[v]!=-1 &
0560: 26 20 76 21 3d 73 20 29 0a 09 09 09 09 09 09 70 & v!=s ).......p
0570: 61 72 65 6e 74 5b 76 5d 20 3d 20 73 3b 0a 09 09 arent[v] = s;...
0580: 09 09 76 65 72 74 20 70 74 20 3d 20 70 61 72 65 ..vert pt = pare
0590: 6e 74 5b 74 5d 3b 0a 09 09 09 09 69 66 28 20 70 nt[t];.....if( p
05a0: 72 65 76 5b 70 74 5d 21 3d 2d 31 20 29 0a 09 09 rev[pt]!=-1 )...
05b0: 09 09 09 70 61 72 65 6e 74 5b 73 5d 3d 70 74 2c ...parent[s]=pt,
05c0: 20 70 61 72 65 6e 74 5b 74 5d 3d 73 2c 20 77 65 parent[t]=s, we
05d0: 69 67 68 74 5b 73 5d 3d 77 65 69 67 68 74 5b 74 ight[s]=weight[t
05e0: 5d 2c 20 77 65 69 67 68 74 5b 74 5d 3d 6d 69 6e ], weight[t]=min
05f0: 63 75 74 3b 0a 09 09 09 09 62 72 65 61 6b 3b 0a cut;.....break;.
0600: 09 09 09 7d 0a 0a 09 09 09 2f 2f 20 66 6c 6f 77 ...}.....// flow
0610: 2e 2e 2e 0a 09 09 09 66 6c 6f 77 20 63 75 72 20 .......flow cur
0620: 3d 20 30 78 37 66 66 66 66 66 66 66 3b 0a 09 09 = 0x7fffffff;...
0630: 09 66 6f 72 28 76 65 72 74 20 76 3d 74 3b 20 76 .for(vert v=t; v
0640: 21 3d 73 3b 20 76 3d 70 72 65 76 5b 76 5d 29 0a !=s; v=prev[v]).
0650: 09 09 09 09 63 75 72 20 3d 20 6d 69 6e 28 63 75 ....cur = min(cu
0660: 72 2c 20 47 48 46 5b 70 72 65 76 5b 76 5d 5d 5b r, GHF[prev[v]][
0670: 76 5d 29 3b 0a 09 09 09 66 6f 72 28 76 65 72 74 v]);....for(vert
0680: 20 76 3d 74 3b 20 76 21 3d 73 3b 20 76 3d 70 72 v=t; v!=s; v=pr
0690: 65 76 5b 76 5d 29 0a 09 09 09 09 47 48 46 5b 70 ev[v]).....GHF[p
06a0: 72 65 76 5b 76 5d 5d 5b 76 5d 20 2d 3d 20 63 75 rev[v]][v] -= cu
06b0: 72 2c 20 47 48 46 5b 76 5d 5b 70 72 65 76 5b 76 r, GHF[v][prev[v
06c0: 5d 5d 20 2b 3d 20 63 75 72 3b 0a 09 09 09 6d 69 ]] += cur;....mi
06d0: 6e 63 75 74 20 2b 3d 20 63 75 72 3b 0a 09 09 7d ncut += cur;...}
06e0: 0a 09 7d 0a 0a 09 2f 2f 20 41 6c 6c 50 61 69 72 ..}...// AllPair
06f0: 4d 69 6e 43 75 74 73 20 6f 76 65 72 20 74 68 65 MinCuts over the
0700: 20 47 2d 48 20 74 72 65 65 0a 09 66 6f 72 28 76 G-H tree..for(v
0710: 65 72 74 20 73 3d 30 3b 20 73 3c 4e 3b 20 2b 2b ert s=0; s<N; ++
0720: 73 29 20 7b 0a 09 09 76 65 63 74 6f 72 3c 76 65 s) {...vector<ve
0730: 72 74 3e 20 70 73 5f 73 3b 0a 09 09 66 6f 72 28 rt> ps_s;...for(
0740: 76 65 72 74 20 76 3d 73 20 3b 3b 20 76 3d 70 61 vert v=s ;; v=pa
0750: 72 65 6e 74 5b 76 5d 29 0a 09 09 09 7b 20 70 73 rent[v])....{ ps
0760: 5f 73 2e 70 75 73 68 5f 62 61 63 6b 28 76 29 3b _s.push_back(v);
0770: 20 69 66 28 20 76 3d 3d 70 61 72 65 6e 74 5b 76 if( v==parent[v
0780: 5d 20 29 20 62 72 65 61 6b 3b 20 7d 0a 09 09 72 ] ) break; }...r
0790: 65 76 65 72 73 65 28 70 73 5f 73 2e 62 65 67 69 everse(ps_s.begi
07a0: 6e 28 29 2c 20 70 73 5f 73 2e 65 6e 64 28 29 29 n(), ps_s.end())
07b0: 3b 0a 0a 09 09 66 6f 72 28 76 65 72 74 20 74 3d ;....for(vert t=
07c0: 73 2b 31 3b 20 74 3c 4e 3b 20 2b 2b 74 29 20 7b s+1; t<N; ++t) {
07d0: 0a 09 09 09 76 65 63 74 6f 72 3c 76 65 72 74 3e ....vector<vert>
07e0: 20 70 73 5f 74 3b 0a 09 09 09 66 6f 72 28 76 65 ps_t;....for(ve
07f0: 72 74 20 76 3d 74 20 3b 3b 20 76 3d 70 61 72 65 rt v=t ;; v=pare
0800: 6e 74 5b 76 5d 29 0a 09 09 09 09 7b 20 70 73 5f nt[v]).....{ ps_
0810: 74 2e 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 20 t.push_back(v);
0820: 69 66 28 20 76 3d 3d 70 61 72 65 6e 74 5b 76 5d if( v==parent[v]
0830: 20 29 20 62 72 65 61 6b 3b 20 7d 0a 09 09 09 72 ) break; }....r
0840: 65 76 65 72 73 65 28 70 73 5f 74 2e 62 65 67 69 everse(ps_t.begi
0850: 6e 28 29 2c 20 70 73 5f 74 2e 65 6e 64 28 29 29 n(), ps_t.end())
0860: 3b 0a 0a 09 09 09 76 65 72 74 20 63 61 3b 0a 09 ;.....vert ca;..
0870: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0880: 3c 70 73 5f 73 2e 73 69 7a 65 28 29 20 26 26 20 <ps_s.size() &&
0890: 69 3c 70 73 5f 74 2e 73 69 7a 65 28 29 20 26 26 i<ps_t.size() &&
08a0: 20 70 73 5f 73 5b 69 5d 3d 3d 70 73 5f 74 5b 69 ps_s[i]==ps_t[i
08b0: 5d 3b 20 2b 2b 69 29 0a 09 09 09 09 63 61 20 3d ]; ++i).....ca =
08c0: 20 70 73 5f 73 5b 69 5d 3b 0a 0a 09 09 09 66 6c ps_s[i];.....fl
08d0: 6f 77 20 73 5f 74 6f 5f 72 6f 6f 74 20 3d 20 30 ow s_to_root = 0
08e0: 78 37 66 66 66 66 66 66 66 2c 20 74 5f 74 6f 5f x7fffffff, t_to_
08f0: 72 6f 6f 74 20 3d 20 30 78 37 66 66 66 66 66 66 root = 0x7ffffff
0900: 66 3b 0a 09 09 09 66 6f 72 28 76 65 72 74 20 76 f;....for(vert v
0910: 3d 73 3b 20 76 21 3d 63 61 3b 20 76 3d 70 61 72 =s; v!=ca; v=par
0920: 65 6e 74 5b 76 5d 29 0a 09 09 09 09 73 5f 74 6f ent[v]).....s_to
0930: 5f 72 6f 6f 74 20 3d 20 6d 69 6e 28 73 5f 74 6f _root = min(s_to
0940: 5f 72 6f 6f 74 2c 20 77 65 69 67 68 74 5b 76 5d _root, weight[v]
0950: 29 3b 0a 09 09 09 66 6f 72 28 76 65 72 74 20 76 );....for(vert v
0960: 3d 74 3b 20 76 21 3d 63 61 3b 20 76 3d 70 61 72 =t; v!=ca; v=par
0970: 65 6e 74 5b 76 5d 29 0a 09 09 09 09 74 5f 74 6f ent[v]).....t_to
0980: 5f 72 6f 6f 74 20 3d 20 6d 69 6e 28 74 5f 74 6f _root = min(t_to
0990: 5f 72 6f 6f 74 2c 20 77 65 69 67 68 74 5b 76 5d _root, weight[v]
09a0: 29 3b 0a 09 09 09 41 6c 6c 50 61 69 72 4d 69 6e );....AllPairMin
09b0: 43 75 74 5b 73 5d 5b 74 5d 20 3d 20 41 6c 6c 50 Cut[s][t] = AllP
09c0: 61 69 72 4d 69 6e 43 75 74 5b 74 5d 5b 73 5d 20 airMinCut[t][s]
09d0: 3d 20 6d 69 6e 28 73 5f 74 6f 5f 72 6f 6f 74 2c = min(s_to_root,
09e0: 20 74 5f 74 6f 5f 72 6f 6f 74 29 3b 0a 09 09 7d t_to_root);...}
09f0: 0a 09 7d 0a 7d 0a ..}.}.