104.md (2673B)
1 Source: https://codeforces.com/blog/entry/2539 2 3 This is translation of author's solution of Div 1 problem E of round 80. 4 5 Italics are [Borisp](https://codeforces.com/profile/Borisp "Лейтенант-полковник Borisp")'s notes. 6 7 | | 8 | --- | 9 | *This problem's statement and Russian solution is by* [winger](https://codeforces.com/profile/winger "Подполковник winger"). Construct bipartite graph *G*1 with available sets on the left side and the numbers on the right side. We put an edge from a set to all the numbers contained in it. By Hall's theorem it follows from "the union of any k sets contains no less than k distinct numbers (for every positive integer k)" that there exists perfect matching of all the elements in the bipartite graph *(in fact the theorem states that there exists matching including all set vertices, but as the numbers are also restricted by n, this means that there exists perfect matching)*. After this observation we find whichever perfect matching in *G*1,let's denote it by *M* = {(*u**i*, *v**i*)}. Now we construct second oriented graph *G*2 with vertices corresponding to the available sets and edges (*u**i* → *u**j*) for each edge (*u**i*, *v**j*) from *G*1 that do not occur in *M (Note that the matching sets the indices of v's and thus we consider them, not the values of the corresponding numbers)*. Now for every suitable collection of size k there should be no outgoing edge to other set in *G*2 (otherwise the numbers included in the sets of the collection will be k plus the additional few numbers from the corresponding outgoing edges and the collection will not be suitable - more numbers than sets). Thus our problem has been transformed to the following equivalent: in an oriented graph with weight of vertices find subset S of the vertices with minimum sum of weights and without outgoing edge with other end not in S. This problem is known to be equivalent to finding minimum cut *(I wasn't able to prove the equivalence, didn't know it by heart either, but I found it even easier to prove if I consider the task as just max flow)* . Assign to the edges of *G*2 infinite weights, add additional vertices *s* and *t*,. Now for every set *u**i* with weight *w* add edge *u**i* → *t* with weight *w* iff *w* > 0 and edge *s* → *u**i* with weight - *w* iff *w* < 0. The part of the minimum cut of s and t in the constructed graph that contains s is the sought optimal collection *(in fact what I did was sum the outgoing weights from s after computing max flow in the graph; I was able to prove this is the required number)*. |