Artifact 3071774087420287802f9927d8945311f4356169:
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 28 4d 69 6e 69 6d 75 6d 29 20 53 65 .// (Minimum) Se
0050: 74 20 43 6f 76 65 72 0a 2f 2f 20 20 20 4e 50 2d t Cover.// NP-
0060: 63 6f 6d 70 6c 65 74 65 0a 2f 2f 0a 2f 2f 20 43 complete.//.// C
0070: 6f 6e 73 69 64 65 72 20 75 73 69 6e 67 20 53 65 onsider using Se
0080: 74 43 6f 76 65 72 45 61 73 79 2c 20 77 68 65 6e tCoverEasy, when
0090: 20 6d 61 73 6b 20 69 73 20 64 6f 77 6e 77 61 72 mask is downwar
00a0: 64 20 63 6c 6f 73 65 64 2e 0a 2f 2f 0a 2f 2f 20 d closed..//.//
00b0: 56 65 72 69 66 69 65 64 20 62 79 0a 2f 2f 20 20 Verified by.//
00c0: 20 2d 20 53 52 4d 33 34 35 20 44 69 76 31 20 4c - SRM345 Div1 L
00d0: 56 33 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d V3.//-----------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
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 0a 0a 4c 4c 20 6e 65 78 74 5f 63 6f 6d 62 --..LL next_comb
0120: 69 6e 61 74 69 6f 6e 28 4c 4c 20 70 29 0a 7b 0a ination(LL p).{.
0130: 09 4c 4c 20 6c 73 62 20 3d 20 70 20 26 20 2d 70 .LL lsb = p & -p
0140: 3b 0a 09 4c 4c 20 72 65 6d 20 3d 20 70 20 2b 20 ;..LL rem = p +
0150: 6c 73 62 3b 0a 09 4c 4c 20 72 69 74 20 3d 20 72 lsb;..LL rit = r
0160: 65 6d 20 26 20 7e 70 3b 0a 09 72 65 74 75 72 6e em & ~p;..return
0170: 20 72 65 6d 7c 28 28 28 72 69 74 2f 6c 73 62 29 rem|(((rit/lsb)
0180: 3e 3e 31 29 2d 31 29 3b 0a 7d 0a 0a 2f 2f 20 49 >>1)-1);.}..// I
0190: 73 20 69 74 20 70 6f 73 73 69 62 6c 65 20 74 6f s it possible to
01a0: 20 63 6f 76 65 72 20 74 68 65 20 67 6f 61 6c 20 cover the goal
01b0: 62 79 20 61 74 20 6d 6f 73 74 20 6b 20 65 6c 65 by at most k ele
01c0: 6d 65 6e 74 73 20 66 72 6f 6d 20 6d 61 73 6b 3f ments from mask?
01d0: 0a 2f 2f 20 41 73 73 75 6d 70 74 69 6f 6e 3a 20 .// Assumption:
01e0: 20 67 6f 61 6c 20 5c 73 75 62 73 65 74 65 71 20 goal \subseteq
01f0: 5c 62 69 67 63 75 70 20 6d 61 73 6b 0a 62 6f 6f \bigcup mask.boo
0200: 6c 20 63 61 6e 43 6f 76 65 72 28 20 4c 4c 20 67 l canCover( LL g
0210: 6f 61 6c 2c 20 73 65 74 3c 4c 4c 3e 26 20 6d 61 oal, set<LL>& ma
0220: 73 6b 2c 20 69 6e 74 20 6b 20 29 0a 7b 0a 09 2f sk, int k ).{../
0230: 2f 20 6f 70 74 69 6d 69 7a 65 72 0a 09 66 6f 72 / optimizer..for
0240: 28 62 6f 6f 6c 20 75 70 64 61 74 65 3d 74 72 75 (bool update=tru
0250: 65 3b 20 75 70 64 61 74 65 3b 20 29 20 7b 0a 09 e; update; ) {..
0260: 09 75 70 64 61 74 65 20 3d 20 66 61 6c 73 65 3b .update = false;
0270: 0a 0a 09 09 2f 2f 20 69 66 20 2a 69 74 20 5c 73 ....// if *it \s
0280: 75 62 73 65 74 65 71 20 2a 6a 74 20 66 6f 72 20 ubseteq *jt for
0290: 73 6f 6d 65 20 6a 74 2c 20 74 68 65 6e 20 77 65 some jt, then we
02a0: 20 4e 45 56 45 52 20 75 73 65 20 69 74 0a 09 09 NEVER use it...
02b0: 2f 2f 20 69 66 20 2a 69 74 20 69 73 20 74 68 65 // if *it is the
02c0: 20 6f 6e 6c 79 20 6d 61 73 6b 20 63 6f 76 65 72 only mask cover
02d0: 69 6e 67 20 73 6f 6d 65 20 63 69 74 79 2c 20 77 ing some city, w
02e0: 65 20 41 4c 57 41 59 53 20 75 73 65 20 69 74 0a e ALWAYS use it.
02f0: 09 09 66 6f 72 28 73 65 74 3c 4c 4c 3e 3a 3a 69 ..for(set<LL>::i
0300: 74 65 72 61 74 6f 72 20 69 74 3d 6d 61 73 6b 2e terator it=mask.
0310: 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 6d 61 73 begin(); it!=mas
0320: 6b 2e 65 6e 64 28 29 3b 20 29 20 7b 0a 09 09 09 k.end(); ) {....
0330: 62 6f 6f 6c 20 69 73 53 75 62 73 65 74 20 3d 20 bool isSubset =
0340: 66 61 6c 73 65 3b 0a 09 09 09 4c 4c 20 20 20 6f false;....LL o
0350: 6e 6c 79 42 79 4d 65 20 3d 20 2a 69 74 20 26 20 nlyByMe = *it &
0360: 67 6f 61 6c 3b 0a 09 09 09 66 6f 72 28 73 65 74 goal;....for(set
0370: 3c 4c 4c 3e 3a 3a 69 74 65 72 61 74 6f 72 20 6a <LL>::iterator j
0380: 74 3d 6d 61 73 6b 2e 62 65 67 69 6e 28 29 3b 20 t=mask.begin();
0390: 6a 74 21 3d 6d 61 73 6b 2e 65 6e 64 28 29 3b 20 jt!=mask.end();
03a0: 2b 2b 6a 74 29 0a 09 09 09 09 69 66 28 20 69 74 ++jt).....if( it
03b0: 21 3d 6a 74 20 29 20 7b 0a 09 09 09 09 09 6f 6e !=jt ) {......on
03c0: 6c 79 42 79 4d 65 20 26 3d 20 7e 2a 6a 74 3b 0a lyByMe &= ~*jt;.
03d0: 09 09 09 09 09 69 73 53 75 62 73 65 74 20 7c 3d .....isSubset |=
03e0: 20 28 2a 69 74 20 26 20 2a 6a 74 20 26 20 67 6f (*it & *jt & go
03f0: 61 6c 29 20 3d 3d 20 28 2a 69 74 20 26 20 67 6f al) == (*it & go
0400: 61 6c 29 3b 0a 09 09 09 09 7d 0a 0a 09 09 09 75 al);.....}.....u
0410: 70 64 61 74 65 20 7c 3d 20 69 73 53 75 62 73 65 pdate |= isSubse
0420: 74 20 7c 20 21 21 6f 6e 6c 79 42 79 4d 65 3b 0a t | !!onlyByMe;.
0430: 0a 09 09 09 69 66 28 20 69 73 53 75 62 73 65 74 ....if( isSubset
0440: 20 29 0a 09 09 09 09 6d 61 73 6b 2e 65 72 61 73 ).....mask.eras
0450: 65 28 69 74 2b 2b 29 3b 0a 09 09 09 65 6c 73 65 e(it++);....else
0460: 20 69 66 28 20 6f 6e 6c 79 42 79 4d 65 20 29 20 if( onlyByMe )
0470: 7b 0a 09 09 09 09 69 66 28 20 2d 2d 6b 20 3c 20 {.....if( --k <
0480: 30 20 29 0a 09 09 09 09 09 72 65 74 75 72 6e 20 0 )......return
0490: 66 61 6c 73 65 3b 0a 09 09 09 09 67 6f 61 6c 20 false;.....goal
04a0: 26 3d 20 7e 2a 69 74 3b 0a 09 09 09 09 6d 61 73 &= ~*it;.....mas
04b0: 6b 2e 65 72 61 73 65 28 69 74 2b 2b 29 3b 0a 09 k.erase(it++);..
04c0: 09 09 7d 0a 09 09 09 65 6c 73 65 0a 09 09 09 09 ..}....else.....
04d0: 2b 2b 69 74 3b 0a 09 09 7d 0a 0a 09 09 69 66 28 ++it;...}....if(
04e0: 20 6d 61 73 6b 2e 73 69 7a 65 28 29 3c 3d 6b 20 mask.size()<=k
04f0: 7c 7c 20 67 6f 61 6c 3d 3d 30 20 29 0a 09 09 09 || goal==0 )....
0500: 72 65 74 75 72 6e 20 74 72 75 65 3b 0a 09 7d 0a return true;..}.
0510: 0a 09 2f 2f 20 65 78 68 61 75 73 74 69 76 65 20 ..// exhaustive
0520: 73 65 61 72 63 68 0a 09 76 65 63 74 6f 72 3c 4c search..vector<L
0530: 4c 3e 20 6d 73 28 6d 61 73 6b 2e 62 65 67 69 6e L> ms(mask.begin
0540: 28 29 2c 20 6d 61 73 6b 2e 65 6e 64 28 29 29 3b (), mask.end());
0550: 0a 09 66 6f 72 28 4c 4c 20 69 3d 28 31 4c 4c 3c ..for(LL i=(1LL<
0560: 3c 6b 29 2d 31 3b 20 69 3c 28 31 4c 4c 3c 3c 6d <k)-1; i<(1LL<<m
0570: 73 2e 73 69 7a 65 28 29 29 3b 20 69 3d 6e 65 78 s.size()); i=nex
0580: 74 5f 63 6f 6d 62 69 6e 61 74 69 6f 6e 28 69 29 t_combination(i)
0590: 29 0a 09 7b 0a 09 09 4c 4c 20 67 67 20 3d 20 67 )..{...LL gg = g
05a0: 6f 61 6c 3b 0a 09 09 66 6f 72 28 4c 4c 20 6a 3d oal;...for(LL j=
05b0: 30 3b 20 28 31 4c 4c 3c 3c 6a 29 3c 3d 69 3b 20 0; (1LL<<j)<=i;
05c0: 2b 2b 6a 29 0a 09 09 09 69 66 28 20 69 20 26 20 ++j)....if( i &
05d0: 28 31 3c 3c 6a 29 20 29 0a 09 09 09 09 67 67 20 (1<<j) ).....gg
05e0: 26 3d 20 7e 6d 73 5b 6a 5d 3b 0a 09 09 69 66 28 &= ~ms[j];...if(
05f0: 20 67 67 20 3d 3d 20 30 20 29 0a 09 09 09 72 65 gg == 0 )....re
0600: 74 75 72 6e 20 74 72 75 65 3b 0a 09 7d 0a 09 72 turn true;..}..r
0610: 65 74 75 72 6e 20 66 61 6c 73 65 3b 0a 7d 0a eturn false;.}.