Simple Scheduling Problem 代码编辑的思想

Problem Description
Team YouAreSoStrong meet a very boring problem. They have to schedule n jobs on m machines. Each job needs exactly one unit time on one machine. At first, YouAreSoStrong thought ceil(n/m) units of time is enough. Soon, they find out there exist some ordering constraints between jobs. This is reasonable. For example, you have to complete "hand in hand" before you can "hug". And only after you've done "hug", can you "kiss". It's guaranteed that following 3 conditions are satisfied.
1. one job can only be relied by at most one job.
2. one job may rely more than one job.
3.There is no circular dependency. Such as a relies on b, and b relies on a.
YouAreSoStrong thought for a long time, but do not have a clue. Can you help them?

Input
First line contains one integer T, indicates the number of test cases. For each case, the first line contains 3 integers : n, e, m, denotes number of jobs, number of ordering constraints, number of machines separately. Each line from 2 to (e+1)th contains one pair of integers (a,b), which stands for job a must be done before job b can start. T≤10. 0 < n, e , m≤100 000.

Output
Print one integer on one line for each case, which is the minimum units of time YouAreSoStrong can schedule all the jobs.

Sample Input
2
4 2 1
1 3
2 3
4 2 2
1 3
2 3

Sample Output
4
2

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐