TopCoder problem "StampsCollection" used in SRM 418 (Division I Level Two)



Problem Statement

    You have decided to sell your stamp collection, which consists of n stamps numbered 0 to n-1. You have already found some buyers. The i-th buyer wants to buy the stamps listed in demand[i]. This will be a space-separated list containing either one or two stamps. He is willing to pay a total of price[i]. If he wants to buy two stamps, he will not agree to buy only one of them.



To make this task simpler, for each stamp, there will be no more than two buyers who want to buy it. Return the maximum amount of money you can get from selling your stamps.
 

Definition

    
Class:StampsCollection
Method:sell
Parameters:int, String[], int[]
Returns:int
Method signature:int sell(int n, String[] demand, int[] price)
(be sure your method is public)
    
 

Notes

-You don't have to sell all of your stamps.
 

Constraints

-n will be between 1 and 50, inclusive.
-demand will contain between 1 and 50 elements, inclusive.
-price will contain the same number of elements as demand.
-Each element of demand will be a space-separated list of one or two distinct integers.
-All numbers in demand will be between 0 and n-1, inclusive, with no leading zeroes.
-All numbers in price will be between 1 and 1000000, inclusive.
-For each stamp, there will be at most 2 buyers who want to buy it.
 

Examples

0)
    
10
{"0 4"}
{3}
Returns: 3
There is only one buyer, so all we can do is to sell two stamps.
1)
    
2
{"1 0","0"}
{3,5}
Returns: 5
There are two buyers, but both want to buy stamp 0.
2)
    
3
{"0 1","0 2","1 2"}
{10,11,12}
Returns: 12
Only one buyer can get what he wants - we choose the third one, who is willing to pay the most.
3)
    
3
{"0","1 0","1 2"}
{5,9,5}
Returns: 10
Although the second buyer will pay the most, it is better to choose the first and third buyers.
4)
    
20
{"0 1","1 2","2 3","3 0","4 5","5 6","6 4","8","8","9","9 10","10 11","11 12","12"}
{3,7,4,1,3,3,1,5,6,5,18,10,1,5}
Returns: 40

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9886

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13509&pm=9886

Writer:

Rydberg

Testers:

PabloGilberto , Olexiy , Mike Mirzayanov , ivan_metelsky , darnley

Problem categories:

Dynamic Programming, Graph Theory