POJ1115 Statistical Trouble翻译

一个电视台转播比赛，电视网络类似于树，树的节点为中转站或者用户
节点的编号为1~N，其中1为总站，2到(N-M)为中转站，(N-M+1)到N为用户
节点到节点间转移信号需要给定的费用，且每个用户愿意出给定的钱付费
在电视台不亏本的前提下，求最多可以让多少用户看到比赛
Your team was hired by the international corporation ACM (Analytical Calculation Maxims). Every year ACM creates and conducts various surveys. Surveys themselves are simple forms with a list of questions and a list of possible answers for every question. Surveys are distributed around the globe, where field agents question the target group of people. All the answers are gathered in the ICPC (International Computation and Processing Center), where teams of well-paid analysts mine raw data in search for relevant correlations. The raw data for each individual survey consists of lots of lines of answers. Each line corresponds to every questioned person and for every question lists answers that the person has made on that particular survey.

The first step of analysis that your team was hired to automate is to create cross tables that correlate answers on interesting pairs of questions. In its most simple way, given a pair of questions, cross table has a row for every possible answer on the first question, and has a column for every possible answer on the second question. Each cell of the cross table contains a number of lines in the raw data that has both answers for the corresponding questions at the same time.

However, your task is complicated by the fact that you are to compute and output not only simple cross table values, but also total values for every row and column in the cross table (that is the sum of values in the corresponding row and column) that are placed in an additional last column and last row, as well as a percentage distributions for every row and column. Percentage distribution for a row is an additional number in every cell in that row that shows percent ratio of the value in that cell to the total value for that row, unless the total value is zero (in that case percentage distribution for this row is not defined). The same applies to the percentage distributions of columns. Thus, the cross table in your output will have at most three values in every cell (the value itself, row-wise percent, and column-wise percent). Please note, that percentage distributions also apply to totals. For example, in the total column for every row the row-wise percent will be always 100%, unless the total value for the row is zero (in that case row-wise percents are not defined), and column -wise percent shows percents ratio of the total value for this row to the total number of lines in the raw data (which is the value that can be found in the last column of the last row).

Percents are rounded to integers on output. Percent that has a non-zero fractional part is rounded to either the smallest integer number greater than the resulting percent, or the largest integer number smaller than the resulting percent, in such a way, that the sums of all corresponding row-wise percents by row (without row totals) or column -wise percents by column (without column totals) are equal to 100% unless they are undefined. There are various rounding algorithms that produce results satisfying the above constraints. You are free to use any rounding algorithm as long as the above constraints are satisfied.
输入：
N M N表示转发站和用户总数，M为用户数
以下N-M行，第i行第一个K，表示转发站i和K个（转发站或用户）相连, 其后第j对数val,cost表示，第i个转发站到val有边，费用cost.
最后一行M个数表示每个用户愿意负的钱。
输出：
不亏本前提下，可以收到节目最多的用户数。
（如果某个用户要收到节目（叶子结点），那么电视台到该用户的路径节点的费用都要付）
Input

The input consists of 3 sections: survey description, survey results, and cross table descriptions.

The first line of the input contains the name of the survey, which is at most 100 characters long. Subsequent lines describe all the questions in the survey. On the first line of every question there is a 3-character question code (capital letters and digits only) followed by a space, and followed by the question name, which is at most 80 characters long. Each subsequent line for a question describes one possible answer on the question and starts with a space, followed by a single-character code for the answer (capital letter, digit, or character ‘.’, ‘*’, or ‘@’), followed by a space and followed by an answer description, which is at most 40 characters long. The list of questions is terminated by the line with a single character ‘#’. All answer codes are unique within the question, and all question codes are unique within the input file. There are at least 2 and at most 10 possible answers per question and at least 2 and at most 100 questions.

Next lines in the input file describe survey results. Every line contains a character per question (in the order they appear in the input file) that gives the answer code for the corresponding question. The characters follow one another without any delimiters. This section is terminated by the line with a single character ‘#’. There is at least one line with answers in the section and at most 10000 answers in total (the number of lines times the number of questions).

Next lines in the input describe cross tables that are to be created. Each cross table description occupies one line. That line contains the code for the first question, followed by a space, followed by the different code for the second question, followed by a space, and followed by the cross table name, which is at most 100 characters long. This section is terminated by the line with a single character ‘#’. There are at most 100 cross table descriptions in the input file.

The input has no trailing spaces on any line. All names do not start or end with a space, but may contain spaces.
Output

Write to the output a cross table for every cross table description in the input file in the order they appear in the input file. On the first line of the cross table write the survey name, followed by a space, followed by a ‘-’ (dash) character, followed by a space, followed by the cross table name. Then write the description of the first question, and the description of the second question exactly as they appear in the input file and in the same format. Then write an empty line, followed by the table itself.

The table contains exactly 1+3*(N1+1) lines and exactly 6*(N2+2) characters on every line, where N1 is the number of possible answers for the first question, and N2 is the number of possible answers for the second question. The table has one line for column headings, and N1+1 rows (3 lines per row). The first N1 of these rows correspond to the answers on the first question in the order they appear in the input file, and the last row is for column totals. The table also has N2+2 columns, where each column is 6 characters wide. The first column is for row headings; the subsequent N2 columns correspond to the answers on the second question in the order they appear in the input file, and the last column is for row totals. All information in the cells (including headings) is aligned to the right and is padded on the left with spaces to become 6 characters wide.

The heading for the first column is empty. The headings for the subsequent N2 columns are composed from the second question code, followed by a ‘:’ (colon) character, and followed by the corresponding answer code. The heading for the last column is the string “TOTAL” (without quotes). The headings for the first N1 3-line rows of the cross table are composed from the first question code, followed by a ‘:’ (colon) character, and followed by the corresponding answer code. The heading for the last row is the string “TOTAL” (without quotes). Row headings are situated on the first line of the corresponding row. The subsequent 2 lines in the heading column of every row must be blank.
All non-heading cells in the table contain computed values and percents. On the first line of every cell the corresponding cross table integer value is situated. The second line contains properly rounded to integers row-wise percent, with a mandatory trailing ‘%’ (percent) character, or a single ‘-’ (dash) character if the corresponding row-wise percent is not defined. The third line contains column -wise percent in the same format. All cross tables in the output file must be separated by a single empty line.