P5225 [CTSC2018] Binomial Coefficient Problem

As everyone knows, student Xiao Cong is good at calculations, especially at computing binomial coefficients. But this problem is not only almost unrelated to binomial coefficients, it is not even related to Xiao Cong. This time, our main character is student Xiao He. As everyone knows, Xiao He is very rich. He bought $K$ TPUs to solve A+B problems. Now Xiao He has $N$ A+B problems. The $i$-th A+B problem needs time $t_{i j}$ to be computed on the $j$-th TPU. Different from traditional A+B problems, there are $M$ dependency relations among these $N$ A+B problems. If problem $i$ depends on problem $j$, then problem $i$ must wait until problem $j$ finishes computing, and after the result is transmitted to the TPU where problem $i$ is located, problem $i$ can start computing. If problem $i$ is computed on the $p$-th TPU and problem $j$ is computed on the $q$-th machine, then the time needed to transmit the result is $r_{p q}$. Data transmission is parallel: multiple machines transmitting to one machine at the same time, or one machine sending data to multiple machines at the same time, will not affect the transmission speed. However, we规定 that data transmission cannot be forwarded: if some data needs to be transmitted from machine $i$ to machine $j$, it cannot be sent to machine $k$ first and then to machine $j$. Although Xiao He is very rich, he does not have much time (after all, he still needs to spend time with girls). So now Xiao He wants you to help him decide which machine each A+B problem should be assigned to, so as to minimize either the total computation time of all TPUs, or the time when all tasks are finished. The “TPU computation time” is defined as the time the TPU spends computing problems plus the sum of all data transmission time. The “all tasks finish time” is defined as the time from the start of the first computation to the end of the last computation. Although Xiao He is very rich, and he knows you do not have much time to do this problem either, to simplify the problem, he makes the following rules for the tasks above: 1. The dependency relations form an acyclic graph. 2. At any moment, one TPU can compute only one problem. Once it starts computing a problem, it will not be interrupted and will keep computing until the problem is finished. 3. If a TPU is currently not computing any problem, and there exists one or more problems whose data is ready for computation, then the TPU will choose the problem with the smallest index among them to start computing. 4. A TPU can perform multiple data transmissions at the same time, and they do not affect each other’s speed. It can also transmit data while computing problems, and the speeds will not affect each other. 5. Data cannot be forwarded; it can only be transmitted directly between the corresponding machines. 6. It is guaranteed that $r_{ii} = 0$. 7. If a task does not depend on other tasks, then the data it needs is already prepared directly on the corresponding machine and does not need transmission. Under the conditions above, Xiao He thinks this problem is simple enough. So he happily goes to have fun with girls and leaves this problem to you.

This is an output-only problem. There are $10$ groups of input data, named `placement1.in` ~ `placement10.in`. The first line contains four integers $N, M, K, op$. If $op = 1$, it means you need to minimize the sum of TPU computation time; otherwise, you need to minimize the completion time of the last finished task. Next $M$ lines each contain two numbers $i, j$, meaning problem $j$ depends on problem $i$. Next $N$ lines each contain $K$ numbers, representing $t_{i j}$. Next $K$ lines each contain $K$ numbers, representing $r_{i j}$.

For each group of input data, you need to submit the corresponding output file `placement1.out` ~ `placement10.out`. One line with $N$ integers, indicating which machine each task is assigned to.

Each test point of this problem has ten scoring criteria. If your answer is less than or equal to the $k$-th criterion among them, then you will get $k$ points for that test point. These criteria are stored in `placement*.ans` in the contestant directory. ### Hint To make it easier for you to test your own answer, Xiao He dumped the girl and then wrote a simulator for you. You can find an executable file `simulator` in your directory. Its usage is to run `./simulator ` in the terminal, where `` is the input file and `` is your answer. It will tell you the total computation time of your assignment scheme and the completion time of all tasks. Note: Since spending time with girls reduced Xiao He’s programming skills, Xiao He cannot guarantee that this simulator will produce correct results for input files not provided by him. Translated by ChatGPT 5