当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2865:ICPC Strikes Again

题目描述
International Concrete Projects Company (ICPC) is a construction company which specializes in building houses for the high-end market. The company is the most profitable company in the world due to a very efficient land division method which has been used in its housing development projects since last year. Recently there was a chaos at ICPC, because employees refused to work arguing that they did not earn enough. Worried about the loss in profit due to the strike, the company board proposed a new method to calculate the salaries which was luckily accepted by everyone.

The salary of a worker reflects the significance of the tasks that he/she has to perform and is influenced by the way tasks depend on each other.

A task X depends on a task Y if either (i) X depends directly on Y, or (ii) there exists a task T such that X depends directly on T and T depends on Y . Since in ICPC all tasks must be performed, there is no circularity in the task dependence relation. Also, a task may be performed by more than one worker.

A basic significance is associated with each task reflecting its importance (for example, developing the efficient land division method is more important than building the houses themselves). The significance of a task T is then defined as the basic significance of T plus the significance of every task which depends directly on T. Note that if no other tasks depend directly on task T, the basic significance and the significance of T are the same.

The salary of a worker is the sum of the significances of all the tasks he/she performs which do not depend on any other task performed by him/her. In other words, a value equal to the significance of task X will be added to the salary of a worker W that works in task X if there is no other task Y on which X depends, and W works also in Y.

ICPC wants you to help them to determine the salary of each of its employees.
输入解释
The input contains several test cases.
The first line of a test case contains two integers T and E indicating respectively the number of tasks and the number of employees (1 <= T <= 1000 and 1 <= E <= 1000). Tasks are numbered from 1 to T and employees from 1 to E.
Then it will come a sequence of lines describing the tasks 1 to T in ascending order. Each task is described by two lines. The first of these lines contains three integers BS, ND and NE, representing respectively the basic significance of the task, the number of tasks that depend directly on it, and the number of employees who perform it (1 <= BS <= 1000, 0 <= ND < T and 1 <= NE <= E). The second line contains ND+NE integers corresponding first to the ND directly dependent tasks and then the NE employees who perform the task.
The end of input is indicated by T = E = 0.
输出解释
Test cases must be answered in the order that they were presented. For each test case you must print:
  • a single line containing five stars ***** indicating the beginning of the case
  • for each employee i, one line with two integers i and s, separated by a blank, meaning that i has a salary of s.
输入样例
3 2
100 2 2
2 3 1 2
40 0 1
1
60 0 1
2
7 2
10 2 1
2 3 1
10 2 1
4 5 2
10 2 1
6 7 2
10 0 1
1
10 0 1
1
10 0 1
1
10 0 1
1
0 0
输出样例
*****
1 200
2 200
*****
1 70
2 60

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 South America 2005

源链接: POJ-2865

最后修改于 2020-10-29T06:46:14+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536