Artifact de8fb2bb9f6a1b6db919912d3742787fd8270ab1:
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 42 69 70 65 72 74 69 74 65 20 6d 61 .// Bipertite ma
0050: 78 2d 6d 61 74 63 68 69 6e 67 20 28 62 79 20 64 x-matching (by d
0060: 75 61 6c 69 74 79 2c 20 6d 69 6e 2d 76 65 72 74 uality, min-vert
0070: 2d 63 6f 76 65 72 29 0a 2f 2f 20 20 20 4f 28 56 -cover).// O(V
0080: 20 45 29 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 E).//.// Verifi
0090: 65 64 20 62 79 0a 2f 2f 20 20 20 53 52 4d 20 33 ed by.// SRM 3
00a0: 39 37 20 44 69 76 31 20 4c 76 33 0a 2f 2f 2d 2d 97 Div1 Lv3.//--
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 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 74 79 70 -----------..typ
00f0: 65 64 65 66 20 69 6e 74 20 20 20 20 20 20 20 20 edef int
0100: 20 20 20 76 65 72 74 3b 0a 74 79 70 65 64 65 66 vert;.typedef
0110: 20 76 65 72 74 20 20 20 20 20 20 20 20 20 20 65 vert e
0120: 64 67 65 3b 0a 74 79 70 65 64 65 66 20 76 65 63 dge;.typedef vec
0130: 74 6f 72 3c 65 64 67 65 3e 20 20 65 64 67 65 73 tor<edge> edges
0140: 3b 0a 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 ;.typedef vector
0150: 3c 65 64 67 65 73 3e 20 67 72 61 70 68 3b 0a 0a <edges> graph;..
0160: 62 6f 6f 6c 20 61 75 67 6d 65 6e 74 28 20 67 72 bool augment( gr
0170: 61 70 68 26 20 47 2c 20 69 6e 74 20 76 2c 20 76 aph& G, int v, v
0180: 65 63 74 6f 72 3c 76 65 72 74 3e 26 20 6d 61 74 ector<vert>& mat
0190: 63 68 54 6f 2c 20 62 6f 6f 6c 20 76 69 73 69 74 chTo, bool visit
01a0: 65 64 5b 5d 20 29 0a 7b 0a 09 66 6f 72 28 69 6e ed[] ).{..for(in
01b0: 74 20 69 3d 30 3b 20 69 3c 47 5b 76 5d 2e 73 69 t i=0; i<G[v].si
01c0: 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0a 09 09 76 ze(); ++i) {...v
01d0: 65 72 74 20 75 20 3d 20 47 5b 76 5d 5b 69 5d 3b ert u = G[v][i];
01e0: 0a 09 09 69 66 28 20 76 69 73 69 74 65 64 5b 75 ...if( visited[u
01f0: 5d 20 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 ] ) continue;...
0200: 76 69 73 69 74 65 64 5b 75 5d 20 3d 20 74 72 75 visited[u] = tru
0210: 65 3b 0a 0a 09 09 69 66 28 20 6d 61 74 63 68 54 e;....if( matchT
0220: 6f 5b 75 5d 3c 30 20 7c 7c 20 61 75 67 6d 65 6e o[u]<0 || augmen
0230: 74 28 47 2c 20 6d 61 74 63 68 54 6f 5b 75 5d 2c t(G, matchTo[u],
0240: 20 6d 61 74 63 68 54 6f 2c 20 76 69 73 69 74 65 matchTo, visite
0250: 64 29 20 29 0a 09 09 09 7b 20 6d 61 74 63 68 54 d) )....{ matchT
0260: 6f 5b 76 5d 3d 75 2c 20 6d 61 74 63 68 54 6f 5b o[v]=u, matchTo[
0270: 75 5d 3d 76 3b 20 72 65 74 75 72 6e 20 74 72 75 u]=v; return tru
0280: 65 3b 20 7d 0a 09 7d 0a 09 72 65 74 75 72 6e 20 e; }..}..return
0290: 66 61 6c 73 65 3b 0a 7d 0a 0a 74 65 6d 70 6c 61 false;.}..templa
02a0: 74 65 3c 69 6e 74 20 4e 56 3e 0a 69 6e 74 20 62 te<int NV>.int b
02b0: 69 4d 61 74 63 68 28 20 67 72 61 70 68 26 20 47 iMatch( graph& G
02c0: 2c 20 69 6e 74 20 4c 20 29 20 2f 2f 20 5b 30 2c , int L ) // [0,
02d0: 4c 29 3a 6c 65 66 74 2c 20 5b 4c 2c 3f 29 3a 72 L):left, [L,?):r
02e0: 69 67 68 74 0a 20 20 20 20 2f 2f 20 6f 6e 6c 79 ight. // only
02f0: 20 6c 65 66 74 2d 3e 72 69 67 68 74 20 65 64 67 left->right edg
0300: 65 73 20 61 72 65 20 75 73 65 64 20 64 75 72 69 es are used duri
0310: 6e 67 20 63 6f 6d 70 75 74 61 74 69 6f 6e 0a 7b ng computation.{
0320: 0a 09 76 65 63 74 6f 72 3c 76 65 72 74 3e 20 6d ..vector<vert> m
0330: 61 74 63 68 54 6f 28 47 2e 73 69 7a 65 28 29 2c atchTo(G.size(),
0340: 20 2d 31 29 3b 0a 09 69 6e 74 20 61 6e 73 20 3d -1);..int ans =
0350: 20 30 3b 0a 09 66 6f 72 28 76 65 72 74 20 76 3d 0;..for(vert v=
0360: 30 3b 20 76 3c 4c 3b 20 2b 2b 76 29 20 7b 0a 09 0; v<L; ++v) {..
0370: 09 62 6f 6f 6c 20 76 69 73 69 74 65 64 5b 4e 56 .bool visited[NV
0380: 5d 20 3d 20 7b 7d 3b 0a 09 09 69 66 28 20 61 75 ] = {};...if( au
0390: 67 6d 65 6e 74 28 47 2c 20 76 2c 20 6d 61 74 63 gment(G, v, matc
03a0: 68 54 6f 2c 20 76 69 73 69 74 65 64 29 20 29 0a hTo, visited) ).
03b0: 09 09 09 2b 2b 61 6e 73 3b 0a 09 7d 0a 09 72 65 ...++ans;..}..re
03c0: 74 75 72 6e 20 61 6e 73 3b 0a 7d 0a turn ans;.}.