2014
04-09

# Simple Scheduling Problem

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?

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.

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.

2
4 2 1
1 3
2 3
4 2 2
1 3
2 3

4
2

#include <cstdio>
#include <deque>
#include <set>
#include <string>
#include <map>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;

#define Debug(x) (cerr << #x << " = " << (x) << endl)
#define Debug2(x, y) (cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl)
template<class T> inline T& RD(T &x){
char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x;
}

const int inf = 0x3f3f3f3f;
const int maxn = 100005;

int ra[maxn];
int d[maxn];
int fa[maxn];

vector<int> v[maxn];

int dfs(int u){
ra[u] = 0;
for(int i=0;i<v[u].size();i++){
ra[u]= max(dfs(v[u][i])+1,ra[u]);
}
return ra[u];
}

int main(){
int T;
scanf("%d",&T);
while(T --){
int n,e,m;
scanf("%d%d%d",&n,&e,&m);
memset(ra,0,sizeof(ra));
memset(d,0,sizeof(d));
memset(fa,0,sizeof(fa));

//build tree
for(int i=1;i<=n;i++)v[i].clear();

for(int i=0;i<e;i++){
int a,b;
scanf("%d%d",&a,&b);
v[b].push_back(a);
fa[a] = 1;
}

//calc the deepth of each node
for(int i=1;i<=n;i++){
if(fa[i] == 0)dfs(i);
}

//calc count of each deepth
int _max = 0;
for(int i=1;i<=n;i++){
d[ra[i]] ++;
_max = max(_max,ra[i]);
}

//cnt: time 	lft: the can-do job last turn left
int cnt = 0,lft = 0;

//if I want to finish d[i] and there is lft left
for(int i=0;i<=_max;i++){
int td = d[i];
//if current time > the deepth, I can use the left;
if(cnt > i){
d[i] -= lft;
//mode lft that I can use
if(d[i] < 0){
lft -= td;
continue;
}
}
//calc the time I should  use and the job left
cnt += d[i]/m;
if(d[i]%m)cnt ++;
lft = m - d[i]%m;
if(lft == m)lft = 0;
}
printf("%d\n", cnt);
}
return 0;
}

1. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。