|
F
|
Next generation contest - 4
|
Time Limit – 5 secs
|
|
Faster Processing
Feasibility
|
|
The era of technology
is so hectic at times! Each & every single day, the crying needs for faster
& faster processors are becoming more important than before with the
continuously increasing complexity of applications & tasks. One of the
solutions that the processor manufacturers are successfully employing nowadays
is parallel processing. Scheduling of tasks is a prime concern while designing
faster processors having several components working in parallel. We are
currently building a new microprocessor that has P logical
sub-processors in it. Each of the logical sub-processors can act as an
individual processor & process one of the available tasks during a time
slot. Note that, a logical sub-processor can process only a single task in one
time slot & a task can not be processed by more than one processor during a
time slot. Now, you are given the arrival time (the time when a task becomes
available to the processors), processing time (the number of time slots
necessary to complete processing the task) & deadline (the earliest time
when the processing of this task is required to be completed) for T tasks.
You have to figure out if it is possible to schedule the tasks using the
available resources in such a way that all tasks are completed before their
respective deadlines.
Let us be a bit more
specific. From now on we shall assume, each time slot equals 1 micro-second.
The span of the first time slot is 0 to 1 micro-second while the second time
slot is 1 to 2 micro-second & so on.
For example, consider a
multi-processor system with 2 logical sub-processors. You are needed to
schedule 3 tasks A, B & C with the following data.
|
Task
|
Arrival
Time
|
Processing
Time
|
Deadline
|
|
A
|
0
|
2
|
2
|
|
B
|
0
|
3
|
4
|
|
C
|
1
|
2
|
3
|
It is possible to
schedule these 3 tasks in the given system so that all the tasks meet their
respective deadlines i.e. processing of task A, B & C are completed at (or
before) time 2 micro-second, 4 micro-second & 3 micro-second respectively.
Look at the following table for a possible schedule.
|
Time
(micro-second)
|
Available
tasks
|
Assigned
to processor - 1
|
Assigned
to processor – 2
|
Completed
tasks
|
Due tasks
|
|
0
|
A,
B
|
A
|
B
|
-
|
-
|
|
1
|
A,
B, C
|
A
|
C
|
-
|
-
|
|
2
|
B,
C
|
B
|
C
|
A
|
A
|
|
3
|
B
|
B
|
-
|
A,
C
|
A,
C
|
|
4
|
-
|
-
|
-
|
A,
C, B
|
A,
C, B
|
Input
The first line of the
input is the number of test cases C (1 ≤ C
≤ 50 ). C test cases follow. A test case begins
with 2 integers P (1 ≤ P
≤ 40) & T(1 ≤ T
≤ 40), as described earlier. Each of the next T
lines gives a task detail. A task detail consists of 3 integers – arrival time,
Ai
(0 ≤ Ai ≤
1000), processing time, Ri (1 ≤ Ri
≤
5000) & deadline, Di (Ai
+
Ri
≤
Di
≤
10000).
Output
For each test case,
print “FEASIBLE” in a line if there is a possible schedule to meet all the
deadlines. Otherwise, print “NO WAY”.
|
Sample Input
|
Output for Sample
Input
|
|
2
2 3
0 2 2
0 3 4
1 2 3
2 3
0 2 2
0 3 3
1 2 3
|
FEASIBLE
NO WAY
|
ProblemSetter: Mohammad Mahmudur Rahman
Special Thanks: Ivan Krasilnikov
由於同一份工作不能在同一個時間並行處理，否則可以使用 greedy 方法。
現在只能使用 maxflow 的方式去分配，為防止點數過多，將時間進行離散化處理。
Dinic's algorithm 效率在此圖效率不錯。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
int x, y, v;// x->y, v
int next;
} edge[10005];
int e, head[505], prev[505], record[505];
int level[505], visited[505];
void addEdge(int x, int y, int v) {
edge[e].x = x, edge[e].y = y, edge[e].v = v;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].v = 0;
edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
memset(level, 0, sizeof(level));
queue<int> Q;
Q.push(s), level[s] = 1;
while(!Q.empty()) {
int tn = Q.front();
Q.pop();
for(int i = head[tn]; i != -1; i = edge[i].next) {
int y = edge[i].y;
if(edge[i].v > 0 && level[y] == 0) {
level[y] = level[tn] + 1;
Q.push(y);
}
}
}
return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
int ret = 0;
stack<int> stk;
memset(visited, 0, sizeof(visited));
stk.push(s);
while(!stk.empty()) {
int now = stk.top();
if(now != t) {
for(int i = head[now]; i != -1; i = edge[i].next) {
int y = edge[i].y;
if(visited[y] || level[y] != level[now] + 1)
continue;
if(edge[i].v > 0) {
stk.push(y), prev[y] = now, record[y] = i;
break;
}
}
if(stk.top() == now)
stk.pop(), visited[now] = 1;
} else {
int flow = 1e+9, bottleneck;
for(int i = t; i != s; i = prev[i]) {
int ri = record[i];
flow = min(flow, edge[ri].v);
}
for(int i = t; i != s; i = prev[i]) {
int ri = record[i];
edge[ri].v -= flow;
edge[ri^1].v += flow;
if(edge[ri].v == 0)
bottleneck = prev[i];
}
while(!stk.empty() && stk.top() != bottleneck)
stk.pop();
ret += flow;
}
}
return ret;
}
int maxflowDinic(int s, int t) {
int flow = 0;
while(buildLevelGraph(s, t))
flow += constructBlockingFlow(s, t);
return flow;
}
int main() {
int n, m;
int testcase;
int i, j, k, x, y;
int P, T;
int l[50], r[50], w[50];
scanf("%d", &testcase);
while(testcase--) {
e = 0;
memset(head, -1, sizeof(head));
scanf("%d %d", &P, &T);
int sum = 0;
set<int> R;
for(i = 0; i < T; i++) {
scanf("%d %d %d", &l[i], &w[i], &r[i]);
sum += w[i];
R.insert(l[i]);
R.insert(r[i]);
}
int source = T + R.size() + 1, sink = source + 1;
for(i = 0; i < T; i++)
addEdge(source, i, w[i]);
int node = T;
for(set<int>::iterator it = R.begin(), jt;
it != R.end(); it++) {
jt = it;
jt++;
if(jt == R.end())
break;
int work = *jt - *it;
for(i = 0; i < T; i++)
if(*it >= l[i] && *it < r[i])
addEdge(i, node, work);
addEdge(node, sink, work * P);
node++;
}
int ret = maxflowDinic(source, sink);
printf("%s\n", ret == sum ? "FEASIBLE" : "NO WAY");
}
return 0;
}
