Artifact b357fd2040b9449a5148cbba3e66c95a567f84ea:
0000: 23 69 6e 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 #include <vector
0010: 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 >.#include <stri
0020: 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 69 6f ng>.#include <io
0030: 73 74 72 65 61 6d 3e 0a 23 69 6e 63 6c 75 64 65 stream>.#include
0040: 20 3c 63 73 74 72 69 6e 67 3e 0a 75 73 69 6e 67 <cstring>.using
0050: 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0a namespace std;.
0060: 0a 0a 0a 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 ....static const
0070: 20 69 6e 74 20 4e 56 20 3d 20 35 31 32 3b 0a 74 int NV = 512;.t
0080: 79 70 65 64 65 66 20 69 6e 74 20 20 20 20 20 20 ypedef int
0090: 20 20 20 20 20 66 6c 6f 77 3b 0a 74 79 70 65 64 flow;.typed
00a0: 65 66 20 69 6e 74 20 20 20 20 20 20 20 20 20 20 ef int
00b0: 20 76 65 72 74 3b 0a 74 79 70 65 64 65 66 20 76 vert;.typedef v
00c0: 65 72 74 20 20 20 20 20 20 20 20 20 20 65 64 67 ert edg
00d0: 65 3b 0a 74 79 70 65 64 65 66 20 76 65 63 74 6f e;.typedef vecto
00e0: 72 3c 65 64 67 65 3e 20 20 65 64 67 65 73 3b 0a r<edge> edges;.
00f0: 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 3c 65 typedef vector<e
0100: 64 67 65 73 3e 20 67 72 61 70 68 3b 0a 74 79 70 dges> graph;.typ
0110: 65 64 65 66 20 66 6c 6f 77 20 20 20 20 20 20 20 edef flow
0120: 20 20 20 66 6c 6f 77 5f 67 72 61 70 68 5b 4e 56 flow_graph[NV
0130: 5d 5b 4e 56 5d 3b 0a 0a 66 6c 6f 77 20 64 69 6e ][NV];..flow din
0140: 69 63 5f 64 66 73 28 20 67 72 61 70 68 26 20 47 ic_dfs( graph& G
0150: 2c 20 66 6c 6f 77 5f 67 72 61 70 68 20 46 2c 20 , flow_graph F,
0160: 76 65 72 74 20 76 2c 20 76 65 72 74 20 44 2c 0a vert v, vert D,.
0170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0180: 69 6e 74 20 4c 56 5b 5d 2c 20 66 6c 6f 77 20 66 int LV[], flow f
0190: 6c 6f 77 5f 69 6e 2c 20 69 6e 74 20 62 6c 6f 63 low_in, int bloc
01a0: 6b 65 64 5b 5d 20 29 0a 7b 0a 09 66 6c 6f 77 20 ked[] ).{..flow
01b0: 66 6c 6f 77 5f 6f 75 74 20 3d 20 30 3b 0a 09 66 flow_out = 0;..f
01c0: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 21 3d 47 or(int i=0; i!=G
01d0: 5b 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 [v].size(); ++i)
01e0: 0a 09 7b 0a 09 09 69 6e 74 20 75 20 3d 20 47 5b ..{...int u = G[
01f0: 76 5d 5b 69 5d 3b 0a 09 09 69 66 28 20 4c 56 5b v][i];...if( LV[
0200: 76 5d 2b 31 3d 3d 4c 56 5b 75 5d 20 26 26 20 46 v]+1==LV[u] && F
0210: 5b 76 5d 5b 75 5d 20 29 0a 09 09 7b 0a 09 09 09 [v][u] )...{....
0220: 66 6c 6f 77 20 66 20 3d 20 6d 69 6e 28 66 6c 6f flow f = min(flo
0230: 77 5f 69 6e 2d 66 6c 6f 77 5f 6f 75 74 2c 20 46 w_in-flow_out, F
0240: 5b 76 5d 5b 75 5d 29 3b 0a 09 09 09 69 66 28 20 [v][u]);....if(
0250: 75 3d 3d 44 20 7c 7c 20 21 62 6c 6f 63 6b 65 64 u==D || !blocked
0260: 5b 75 5d 20 26 26 20 28 66 3d 64 69 6e 69 63 5f [u] && (f=dinic_
0270: 64 66 73 28 47 2c 46 2c 75 2c 44 2c 4c 56 2c 66 dfs(G,F,u,D,LV,f
0280: 2c 62 6c 6f 63 6b 65 64 29 29 20 29 0a 09 09 09 ,blocked)) )....
0290: 7b 0a 09 09 09 09 46 5b 76 5d 5b 75 5d 20 20 2d {.....F[v][u] -
02a0: 3d 20 66 3b 0a 09 09 09 09 46 5b 75 5d 5b 76 5d = f;.....F[u][v]
02b0: 20 20 2b 3d 20 66 3b 0a 09 09 09 09 66 6c 6f 77 += f;.....flow
02c0: 5f 6f 75 74 20 2b 3d 20 66 3b 0a 09 09 09 09 69 _out += f;.....i
02d0: 66 28 20 66 6c 6f 77 5f 69 6e 20 3d 3d 20 66 6c f( flow_in == fl
02e0: 6f 77 5f 6f 75 74 20 29 20 72 65 74 75 72 6e 20 ow_out ) return
02f0: 66 6c 6f 77 5f 6f 75 74 3b 0a 09 09 09 7d 0a 09 flow_out;....}..
0300: 09 7d 0a 09 7d 0a 09 62 6c 6f 63 6b 65 64 5b 76 .}..}..blocked[v
0310: 5d 20 3d 20 28 66 6c 6f 77 5f 6f 75 74 3d 3d 30 ] = (flow_out==0
0320: 29 3b 0a 09 72 65 74 75 72 6e 20 66 6c 6f 77 5f );..return flow_
0330: 6f 75 74 3b 0a 7d 0a 0a 66 6c 6f 77 20 64 69 6e out;.}..flow din
0340: 69 63 28 20 67 72 61 70 68 26 20 47 2c 20 66 6c ic( graph& G, fl
0350: 6f 77 5f 67 72 61 70 68 20 46 2c 20 76 65 72 74 ow_graph F, vert
0360: 20 53 2c 20 76 65 72 74 20 44 20 29 0a 7b 0a 09 S, vert D ).{..
0370: 66 6f 72 28 20 66 6c 6f 77 20 74 6f 74 61 6c 3d for( flow total=
0380: 30 20 3b 3b 20 29 20 7b 0a 09 09 69 6e 74 20 4c 0 ;; ) {...int L
0390: 56 5b 4e 56 5d 20 3d 20 7b 30 7d 3b 0a 09 09 76 V[NV] = {0};...v
03a0: 65 63 74 6f 72 3c 69 6e 74 3e 20 51 28 31 2c 20 ector<int> Q(1,
03b0: 53 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6c 76 S);...for(int lv
03c0: 3d 31 3b 20 21 51 2e 65 6d 70 74 79 28 29 3b 20 =1; !Q.empty();
03d0: 2b 2b 6c 76 29 0a 09 09 7b 0a 09 09 09 76 65 63 ++lv)...{....vec
03e0: 74 6f 72 3c 69 6e 74 3e 20 51 32 3b 0a 09 09 09 tor<int> Q2;....
03f0: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 21 3d for(int i=0; i!=
0400: 51 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 Q.size(); ++i)..
0410: 09 09 7b 0a 09 09 09 09 65 64 67 65 73 26 20 6e ..{.....edges& n
0420: 65 20 3d 20 47 5b 51 5b 69 5d 5d 3b 0a 09 09 09 e = G[Q[i]];....
0430: 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 21 .for(int j=0; j!
0440: 3d 6e 65 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 =ne.size(); ++j)
0450: 0a 09 09 09 09 09 69 66 28 20 46 5b 51 5b 69 5d ......if( F[Q[i]
0460: 5d 5b 6e 65 5b 6a 5d 5d 20 26 26 20 21 4c 56 5b ][ne[j]] && !LV[
0470: 6e 65 5b 6a 5d 5d 20 26 26 20 6e 65 5b 6a 5d 21 ne[j]] && ne[j]!
0480: 3d 53 20 29 0a 09 09 09 09 09 09 4c 56 5b 6e 65 =S ).......LV[ne
0490: 5b 6a 5d 5d 3d 6c 76 2c 20 51 32 2e 70 75 73 68 [j]]=lv, Q2.push
04a0: 5f 62 61 63 6b 28 6e 65 5b 6a 5d 29 3b 0a 09 09 _back(ne[j]);...
04b0: 09 7d 0a 09 09 09 51 2e 73 77 61 70 28 51 32 29 .}....Q.swap(Q2)
04c0: 3b 0a 09 09 7d 0a 0a 09 09 69 66 28 20 21 4c 56 ;...}....if( !LV
04d0: 5b 44 5d 20 29 0a 09 09 09 72 65 74 75 72 6e 20 [D] )....return
04e0: 74 6f 74 61 6c 3b 0a 0a 09 09 69 6e 74 20 62 6c total;....int bl
04f0: 6f 63 6b 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b 0a ocked[NV] = {};.
0500: 09 09 74 6f 74 61 6c 20 2b 3d 20 64 69 6e 69 63 ..total += dinic
0510: 5f 64 66 73 28 20 47 2c 20 46 2c 20 53 2c 20 44 _dfs( G, F, S, D
0520: 2c 20 4c 56 2c 20 30 78 37 66 66 66 66 66 66 66 , LV, 0x7fffffff
0530: 2c 20 62 6c 6f 63 6b 65 64 20 29 3b 0a 09 7d 0a , blocked );..}.
0540: 7d 0a 0a 0a 0a 73 74 72 75 63 74 20 44 61 6e 63 }....struct Danc
0550: 69 6e 67 50 61 72 74 79 0a 7b 0a 09 69 6e 74 20 ingParty.{..int
0560: 6d 61 78 44 61 6e 63 65 73 28 76 65 63 74 6f 72 maxDances(vector
0570: 3c 73 74 72 69 6e 67 3e 20 6c 69 6b 65 73 2c 20 <string> likes,
0580: 69 6e 74 20 6b 29 0a 09 7b 0a 09 09 69 6e 74 20 int k)..{...int
0590: 6e 20 3d 20 6c 69 6b 65 73 2e 73 69 7a 65 28 29 n = likes.size()
05a0: 3b 0a 09 09 23 64 65 66 69 6e 65 20 53 52 43 20 ;...#define SRC
05b0: 30 0a 09 09 23 64 65 66 69 6e 65 20 44 53 54 20 0...#define DST
05c0: 31 0a 09 09 23 64 65 66 69 6e 65 20 4c 28 69 29 1...#define L(i)
05d0: 20 20 32 2b 6e 2a 30 2b 69 0a 09 09 23 64 65 66 2+n*0+i...#def
05e0: 69 6e 65 20 52 28 69 29 20 20 32 2b 6e 2a 31 2b ine R(i) 2+n*1+
05f0: 69 0a 09 09 23 64 65 66 69 6e 65 20 59 4c 28 69 i...#define YL(i
0600: 29 20 32 2b 6e 2a 32 2b 69 0a 09 09 23 64 65 66 ) 2+n*2+i...#def
0610: 69 6e 65 20 4e 4c 28 69 29 20 32 2b 6e 2a 33 2b ine NL(i) 2+n*3+
0620: 69 0a 09 09 23 64 65 66 69 6e 65 20 59 52 28 69 i...#define YR(i
0630: 29 20 32 2b 6e 2a 34 2b 69 0a 09 09 23 64 65 66 ) 2+n*4+i...#def
0640: 69 6e 65 20 4e 52 28 69 29 20 32 2b 6e 2a 35 2b ine NR(i) 2+n*5+
0650: 69 0a 0a 09 09 67 72 61 70 68 20 47 28 32 2b 6e i....graph G(2+n
0660: 2a 36 29 3b 0a 0a 09 09 2f 2f 20 47 72 61 70 68 *6);....// Graph
0670: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0680: 69 3c 6e 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 47 i<n; ++i) {....G
0690: 5b 53 52 43 20 5d 2e 70 75 73 68 5f 62 61 63 6b [SRC ].push_back
06a0: 28 4c 28 69 29 29 3b 20 20 47 5b 4c 28 69 29 20 (L(i)); G[L(i)
06b0: 5d 2e 70 75 73 68 5f 62 61 63 6b 28 53 52 43 29 ].push_back(SRC)
06c0: 3b 0a 09 09 09 47 5b 4c 28 69 29 5d 2e 70 75 73 ;....G[L(i)].pus
06d0: 68 5f 62 61 63 6b 28 59 4c 28 69 29 29 3b 20 47 h_back(YL(i)); G
06e0: 5b 59 4c 28 69 29 5d 2e 70 75 73 68 5f 62 61 63 [YL(i)].push_bac
06f0: 6b 28 4c 28 69 29 29 3b 0a 09 09 09 47 5b 4c 28 k(L(i));....G[L(
0700: 69 29 5d 2e 70 75 73 68 5f 62 61 63 6b 28 4e 4c i)].push_back(NL
0710: 28 69 29 29 3b 20 47 5b 4e 4c 28 69 29 5d 2e 70 (i)); G[NL(i)].p
0720: 75 73 68 5f 62 61 63 6b 28 4c 28 69 29 29 3b 0a ush_back(L(i));.
0730: 0a 09 09 09 47 5b 44 53 54 20 5d 2e 70 75 73 68 ....G[DST ].push
0740: 5f 62 61 63 6b 28 52 28 69 29 29 3b 20 20 47 5b _back(R(i)); G[
0750: 52 28 69 29 20 5d 2e 70 75 73 68 5f 62 61 63 6b R(i) ].push_back
0760: 28 44 53 54 29 3b 0a 09 09 09 47 5b 52 28 69 29 (DST);....G[R(i)
0770: 5d 2e 70 75 73 68 5f 62 61 63 6b 28 59 52 28 69 ].push_back(YR(i
0780: 29 29 3b 20 47 5b 59 52 28 69 29 5d 2e 70 75 73 )); G[YR(i)].pus
0790: 68 5f 62 61 63 6b 28 52 28 69 29 29 3b 0a 09 09 h_back(R(i));...
07a0: 09 47 5b 52 28 69 29 5d 2e 70 75 73 68 5f 62 61 .G[R(i)].push_ba
07b0: 63 6b 28 4e 52 28 69 29 29 3b 20 47 5b 4e 52 28 ck(NR(i)); G[NR(
07c0: 69 29 5d 2e 70 75 73 68 5f 62 61 63 6b 28 52 28 i)].push_back(R(
07d0: 69 29 29 3b 0a 0a 09 09 09 66 6f 72 28 69 6e 74 i));.....for(int
07e0: 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b 6a 29 0a j=0; j<n; ++j).
07f0: 09 09 09 09 69 66 28 20 6c 69 6b 65 73 5b 69 5d ....if( likes[i]
0800: 5b 6a 5d 20 3d 3d 20 27 59 27 20 29 0a 09 09 09 [j] == 'Y' )....
0810: 09 09 47 5b 59 4c 28 69 29 5d 2e 70 75 73 68 5f ..G[YL(i)].push_
0820: 62 61 63 6b 28 59 52 28 6a 29 29 2c 20 47 5b 59 back(YR(j)), G[Y
0830: 52 28 6a 29 5d 2e 70 75 73 68 5f 62 61 63 6b 28 R(j)].push_back(
0840: 59 4c 28 69 29 29 3b 0a 09 09 09 09 65 6c 73 65 YL(i));.....else
0850: 0a 09 09 09 09 09 47 5b 4e 4c 28 69 29 5d 2e 70 ......G[NL(i)].p
0860: 75 73 68 5f 62 61 63 6b 28 4e 52 28 6a 29 29 2c ush_back(NR(j)),
0870: 20 47 5b 4e 52 28 6a 29 5d 2e 70 75 73 68 5f 62 G[NR(j)].push_b
0880: 61 63 6b 28 4e 4c 28 69 29 29 3b 0a 09 09 7d 0a ack(NL(i));...}.
0890: 0a 09 09 66 6f 72 28 69 6e 74 20 4d 3d 31 3b 20 ...for(int M=1;
08a0: 4d 3c 3d 6e 3b 20 2b 2b 4d 29 20 7b 0a 09 09 09 M<=n; ++M) {....
08b0: 2f 2f 20 46 6c 6f 77 0a 09 09 09 66 6c 6f 77 5f // Flow....flow_
08c0: 67 72 61 70 68 20 46 20 3d 20 7b 7d 3b 0a 09 09 graph F = {};...
08d0: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
08e0: 6e 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 46 5b n; ++i) {.....F[
08f0: 53 52 43 5d 5b 4c 28 69 29 5d 20 3d 20 4d 3b 0a SRC][L(i)] = M;.
0900: 09 09 09 09 46 5b 4c 28 69 29 5d 5b 59 4c 28 69 ....F[L(i)][YL(i
0910: 29 5d 20 3d 20 4d 3b 0a 09 09 09 09 46 5b 4c 28 )] = M;.....F[L(
0920: 69 29 5d 5b 4e 4c 28 69 29 5d 20 3d 20 6b 3b 0a i)][NL(i)] = k;.
0930: 0a 09 09 09 09 46 5b 52 28 69 29 5d 5b 44 53 54 .....F[R(i)][DST
0940: 5d 20 3d 20 4d 3b 0a 09 09 09 09 46 5b 59 52 28 ] = M;.....F[YR(
0950: 69 29 5d 5b 52 28 69 29 5d 20 3d 20 4d 3b 0a 09 i)][R(i)] = M;..
0960: 09 09 09 46 5b 4e 52 28 69 29 5d 5b 52 28 69 29 ...F[NR(i)][R(i)
0970: 5d 20 3d 20 6b 3b 0a 0a 09 09 09 09 66 6f 72 28 ] = k;......for(
0980: 69 6e 74 20 6a 3d 30 3b 20 6a 3c 6e 3b 20 2b 2b int j=0; j<n; ++
0990: 6a 29 0a 09 09 09 09 09 69 66 28 20 6c 69 6b 65 j)......if( like
09a0: 73 5b 69 5d 5b 6a 5d 20 3d 3d 20 27 59 27 20 29 s[i][j] == 'Y' )
09b0: 0a 09 09 09 09 09 09 46 5b 59 4c 28 69 29 5d 5b .......F[YL(i)][
09c0: 59 52 28 6a 29 5d 20 3d 20 31 3b 0a 09 09 09 09 YR(j)] = 1;.....
09d0: 09 65 6c 73 65 0a 09 09 09 09 09 09 46 5b 4e 4c .else.......F[NL
09e0: 28 69 29 5d 5b 4e 52 28 6a 29 5d 20 3d 20 31 3b (i)][NR(j)] = 1;
09f0: 0a 09 09 09 7d 0a 0a 09 09 09 2f 2f 20 4d 61 78 ....}.....// Max
0a00: 66 6c 6f 77 0a 09 09 09 69 66 28 20 64 69 6e 69 flow....if( dini
0a10: 63 28 47 2c 20 46 2c 20 53 52 43 2c 20 44 53 54 c(G, F, SRC, DST
0a20: 29 20 3c 20 4d 2a 6e 20 29 0a 09 09 09 09 72 65 ) < M*n ).....re
0a30: 74 75 72 6e 20 4d 2d 31 3b 0a 09 09 7d 0a 09 09 turn M-1;...}...
0a40: 72 65 74 75 72 6e 20 6e 3b 0a 09 7d 0a 7d 3b 0a return n;..}.};.