Task Schedule
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4003 Accepted Submission(s): 1347
Problem Description
Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory
has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted
and processed on different machines on different days.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.
has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted
and processed on different machines on different days.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.
Input
On the first line comes an integer T(T<=20), indicating the number of test cases.
You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible
schedule every task that can be finished will be done before or at its end day.
You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible
schedule every task that can be finished will be done before or at its end day.
Output
For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.
Print a blank line after each test case.
Print a blank line after each test case.
Sample Input
2
4 3
1 3 5
1 1 4
2 3 7
3 5 9 2 2
2 1 3
1 2 2
Sample Output
Case 1: Yes Case 2: Yes
Author
allenlowesy
Source
题意：有n个机器，m项任务，每一个任务须要Pi天时间，开工日期到收工日期为Si到Ei。一次仅仅能在一台机器上加工，能够挪到别的机器上，问是否能按期完毕全部任务。
题解：这题关键在构图，设置一个源点到每项任务有一条边，容量为该项任务所须要的天数，每项任务到合法加工日期内的每一个天数加一条边，容量为1，即每天工作量为1。然后每一个天数到汇点加入一条边，容量为机器数量n。表示一天最大加工量。
218ms
#include <stdio.h>
#include <string.h> #define maxn 1200
#define maxm 700000
#define inf 0x3f3f3f3f int head[maxn], n, m, id; // n machines
struct Node {
int u, v, c, next;
} E[maxm];
int source, sink, tar, maxDay, nv;
int que[maxn], Layer[maxn], pre[maxn];
bool vis[maxn]; void addEdge(int u, int v, int c) {
E[id].u = u; E[id].v = v;
E[id].c = c; E[id].next = head[u];
head[u] = id++; E[id].u = v; E[id].v = u;
E[id].c = 0; E[id].next = head[v];
head[v] = id++;
} void getMap() {
int i, j, u, v, p, s, e;
id = tar = maxDay = 0;
scanf("%d%d", &m, &n);
memset(head, -1, sizeof(head));
source = 0; sink = 705;
for(i = 1; i <= m; ++i) {
scanf("%d%d%d", &p, &s, &e);
tar += p;
if(e > maxDay) maxDay = e;
addEdge(source, i, p);
for(j = s; j <= e; ++j)
addEdge(i, m + j, 1);
}
sink = m + maxDay + 1; nv = sink + 1;
for(i = 1; i <= maxDay; ++i)
addEdge(m + i, sink, n);
} bool countLayer() {
memset(Layer, 0, sizeof(int) * nv);
int id = 0, front = 0, u, v, i;
Layer[source] = 1; que[id++] = source;
while(front != id) {
u = que[front++];
for(i = head[u]; i != -1; i = E[i].next) {
v = E[i].v;
if(E[i].c && !Layer[v]) {
Layer[v] = Layer[u] + 1;
if(v == sink) return true;
else que[id++] = v;
}
}
}
return false;
} int Dinic() {
int i, u, v, minCut, maxFlow = 0, pos, id = 0;
while(countLayer()) {
memset(vis, 0, sizeof(bool) * nv);
memset(pre, -1, sizeof(int) * nv);
que[id++] = source; vis[source] = 1;
while(id) {
u = que[id - 1];
if(u == sink) {
minCut = inf;
for(i = pre[sink]; i != -1; i = pre[E[i].u])
if(minCut > E[i].c) {
minCut = E[i].c; pos = E[i].u;
}
maxFlow += minCut;
for(i = pre[sink]; i != -1; i = pre[E[i].u]) {
E[i].c -= minCut;
E[i^1].c += minCut;
}
while(que[id-1] != pos)
vis[que[--id]] = 0;
} else {
for(i = head[u]; i != -1; i = E[i].next)
if(E[i].c && Layer[u] + 1 == Layer[v = E[i].v] && !vis[v]) {
vis[v] = 1; que[id++] = v; pre[v] = i; break;
}
if(i == -1) --id;
}
}
}
return maxFlow;
} void solve(int cas) {
printf("Case %d: %s\n\n", cas, tar == Dinic() ? "Yes" : "No");
} int main() {
// freopen("stdin.txt", "r", stdin);
int t, cas;
scanf("%d", &t);
for(cas = 1; cas <= t; ++cas) {
getMap();
solve(cas);
}
return 0;
}
62ms
#include <stdio.h>
#include <string.h> #define maxn 1200
#define maxm 700000 int head[maxn], n, m, id; // n machines
struct Node {
int u, v, c, next;
} E[maxm];
int source, sink, tar, maxDay, nv; const int inf = 0x3f3f3f3f; int cur[maxn], ps[maxn], dep[maxn]; void addEdge(int u, int v, int c) {
E[id].u = u; E[id].v = v;
E[id].c = c; E[id].next = head[u];
head[u] = id++; E[id].u = v; E[id].v = u;
E[id].c = 0; E[id].next = head[v];
head[v] = id++;
} void getMap() {
int i, j, u, v, p, s, e;
id = tar = maxDay = 0;
scanf("%d%d", &m, &n);
memset(head, -1, sizeof(head));
source = 0;
for(i = 1; i <= m; ++i) {
scanf("%d%d%d", &p, &s, &e);
tar += p;
if(e > maxDay) maxDay = e;
addEdge(source, i, p);
for(j = s; j <= e; ++j)
addEdge(i, m + j, 1);
}
sink = m + maxDay + 1; nv = sink + 1;
for(i = 1; i <= maxDay; ++i)
addEdge(m + i, sink, n);
} // 參数：顶点个数。源点，汇点
int Dinic(int n, int s, int t) {
int tr, res = 0;
int i, j, k, f, r, top;
while(true) {
memset(dep, -1, n * sizeof(int));
for(f = dep[ps[0] = s] = 0, r = 1; f != r; )
for(i = ps[f++], j = head[i]; j != -1; j = E[j].next) {
if(E[j].c && -1 == dep[k=E[j].v]) {
dep[k] = dep[i] + 1; ps[r++] = k;
if(k == t) {
f = r; break;
}
}
}
if(-1 == dep[t]) break; memcpy(cur, head, n * sizeof(int));
for(i = s, top = 0; ; ) {
if(i == t) {
for(k = 0, tr = inf; k < top; ++k)
if(E[ps[k]].c < tr) tr = E[ps[f=k]].c;
for(k = 0; k < top; ++k)
E[ps[k]].c -= tr, E[ps[k]^1].c += tr;
res += tr; i = E[ps[top = f]].u;
}
for(j = cur[i]; cur[i] != -1; j = cur[i] = E[cur[i]].next)
if(E[j].c && dep[i] + 1 == dep[E[j].v]) break;
if(cur[i] != -1) {
ps[top++] = cur[i];
i = E[cur[i]].v;
} else {
if(0 == top) break;
dep[i] = -1; i = E[ps[--top]].u;
}
}
}
return res;
} void solve(int cas) {
printf("Case %d: %s\n\n", cas, tar == Dinic(nv, source, sink) ? "Yes" : "No");
} int main() {
// freopen("stdin.txt", "r", stdin);
int t, cas;
scanf("%d", &t);
for(cas = 1; cas <= t; ++cas) {
getMap();
solve(cas);
}
return 0;
}