P2762 Space Flight Planning Problem

Professor W is planning a series of space flights for the National Space Center. Each space flight can carry out a series of commercial experiments to earn profit. A set of optional experiments has been determined as $ E = \{ E_1, E_2, \cdots, E_m \} $, and the set of all instruments required to conduct these experiments is $ I = \{ I_1, I_2, \cdots, I_n \} $. The instruments required by experiment $ E_j $ form a subset $ R_j \subseteq I $. The cost to configure instrument $ I_k $ is $ c_k $ dollars. The sponsors of experiment $ E_j $ have agreed to pay $ p_j $ dollars for its results. Professor W’s task is to design an efficient algorithm to determine which experiments to conduct and thus which instruments to configure in a single space flight to maximize the net profit. Here, the net profit is defined as the total income from the experiments minus the total cost of configuring the instruments. Given the experiments and instrument configuration information, write a program to find the plan with the maximum net profit.

The first line contains $ 2 $ positive integers $ m $ and $ n $. Here, $ m $ is the number of experiments and $ n $ is the number of instruments. The next $ m $ lines each describe one experiment. The first number is the payment the sponsor agrees to pay for that experiment, followed by the indices of the instruments required by that experiment. The last line contains $ n $ numbers, which are the configuration costs of each instrument.

The first line contains the indices of the selected experiments. The second line contains the indices of the selected instruments. The last line contains the net profit.

Thanks to @FlierKing for providing the SPJ. Constraints: $ 1 \leq n, m \leq 50, 1 \leq c, p < 2^{31} $. The testdata for this problem was generated on Windows. All line breaks in the input are `\r\n` instead of `\n` . When reading the indices of the instruments required by an experiment, you can read them as follows. (Thanks to @zhouyonglong.) ```cpp char tools[10000]; memset(tools,0,sizeof tools); cin.getline(tools,10000); int ulen=0,tool; while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用 {//tool是该实验所需仪器的其中一个 //这一行，你可以将读进来的编号进行储存、处理，如连边。 if (tool==0) ulen++; else { while (tool) { tool/=10; ulen++; } } ulen++; } ``` Translated by ChatGPT 5