There is a set of items. You are given some subsets of these items. (each has a given price)
You should calculate how much money you need to spend to have a full set and which subsets you need to buy.
(Number of subsets is <= 3000)
(It is not guaranteed that there is a solution)
Easier version: You know that the main set is {1,2,3,4,5,6,7,8,9,10,11,12,13}
Example for easier version:
1,2,3 price: 3
4,5,6 price: 3
7,8,9 price: 3
10,11,12 price: 3
13 price: 100
1,2,3,4,5,6,7,8,9,10,11,12,13 price: 110
The answer is obviously 110. (you only need to buy a last one, they dont have to be proper subsets)
Does anybody know the solution? Is something similar here on CF?
Maybe it's mincost max flow (mb there is easier solution, idk).
I also don't know if this solution will pass the time limit.
For example A is origin, B is sink, Si — subset no. i.
Max flow should be |items| if there is an answer, minimal cost will be the minimal price.
Why downvotes? It’s true solution.
This is a harder version of set cover problem and therefore is np hard. The easier version can be solved using bitmasks.
But how?? I cant find a place where the algorithm is explained.