Space Flight Planning

Problem Source

Network Flow 24 Problems

Problem Description

Professor W is planning a series of space flights for the national aerospace center. Each space flight can carry out a series of commercial experiments and earn profit. A set of selectable experiments $E = \{ E_1, E_2, \cdots, E_m \}$ has been determined, as well as the set $I = \{ I_1, I_2, \cdots, I_n \}$ of all instruments needed to conduct these experiments. Experiment $E_j$ requires the subset $R_j \subseteq I$ of instruments.

Configuring instrument $I_k$ costs $c_k$ dollars. The sponsor of experiment $E_j$ has agreed to pay $p_j$ dollars for its results. Professor W's task is to find an efficient algorithm that decides which experiments to conduct on one space flight, and therefore which instruments to configure, so as to maximize the net profit of the space flight. Here net profit is the difference between the total income from the conducted experiments and the total cost of configuring the instruments.

Given the configuration of experiments and instruments, write a program that finds the experiment plan with the maximum net profit.

Input Format

The first line contains $2$ positive integers $m, n (1\leq m, n\leq 50)$. $m$ is the number of experiments, $n$ is the number of instruments. The following $m$ lines each contain the data of one experiment. The first number is the fee the sponsor agrees to pay for this experiment; followed by the indices of the several instruments this experiment needs. The last line contains $n$ numbers: the cost of configuring each instrument.

Output Format

The first line is the experiment indices, the second line is the instrument indices, and the last line is the net profit.

Sample Input

2 3
10 1 2
25 2 3
5 6 7

Sample Output

1 2
1 2 3
17

Hint

Reference input code:

std::cin >> m >> n;
    std::string str;
    std::getline(std::cin, str);
    for (int i = 1; i <= m; i++) {
        std::getline(std::cin, str);

        std::stringstream ss;
        ss << str;

        int x;
        ss >> x;

        while (!ss.eof()) {
            ss >> x;
        }
    }

• This is the classic "maximum-weight closed subgraph" problem, solvable with minimum cut: connect a source to each experiment with capacity = its profit, each instrument to the sink with capacity = its cost, and each experiment to the instruments it needs with infinite capacity. The maximum net profit is total experiment profit minus the minimum cut.