Task Schedule（HDOJ 3572）
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.
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.
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.
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
My Code
有n个任务和m台机器，每个任务可以在第si到第ei天内任选pi天完成。
（1）每天只能同时做m个任务，因为只有m台机器，每台机器只能同时做一个任务。
（2）每个任务同时只能有由一个机器做，所以每个任务需要做pi天
首先建立一个超级源点，然后和每个任务连起来，容量为pi，如果这n个弧都满流就说明，所有任务都完成了。
每个任务和si到ei的每一天连起来，容量为1，因为第（2）条
最后每一天都和超级汇点连起来，容量为m，因为第（1）条
剩下的就跑最大流了，如果最大流等于∑pi，就说明任务完成了
#include
#include
#include
#define maxn 1005
#define maxm 250005
#define inf 0x3f3f3f3f
using namespace std;
int T;
int n, m;
struct edge
{
int v;
int c;
int next;
} e[maxm << 1];
int tot;
int cnt;
int head[maxn];
int cur[maxn];
void add(int u, int v, int c)
{
e[++tot].v = v;
e[tot].c = c;
e[tot].next = head[u];
head[u] = tot;
}
int dep[maxn];
bool bfs(int s, int t)
{
queue q;
memset(dep, 0, sizeof(dep));
dep[s] = 1;
q.push(s);
for (int i = 0; i <= t; i++) //总的点数不是n，而是t+1
cur[i] = head[i];
while (!q.empty())
{
s = q.front();
q.pop();
for (int i = head[s]; ~i; i = e[i].next)
if (e[i].c && !dep[e[i].v])
{
dep[e[i].v] = dep[s] + 1;
if (e[i].v == t)
return true;
q.push(e[i].v);
}
}
return false;
}
int dfs(int s, int t, int flow)
{
if (s == t || !flow)
return flow;
int ans = 0;
for (int &i = cur[s]; ~i; i = e[i].next)
if (e[i].c && dep[e[i].v] == dep[s] + 1)
{
int res = dfs(e[i].v, t, min(flow, e[i].c));
if (!res)
dep[e[i].v] = 0;
e[i].c -= res;
e[i ^ 1].c += res;
ans += res;
flow -= res;
if (!flow)
break;
}
return ans;
}
void init()
{
memset(e, -1, sizeof(e));
memset(head, -1, sizeof(head));
tot = -1;
}
int dinic(int s, int t)
{
int ans = 0;
while (bfs(s, t))
ans += dfs(s, t, inf);
return ans;
}
int main()
{
cin >> T;
while (T--)
{
init();
cin >> n >> m;
int sum = 0;
int maxd = 0;
int s = 0;
for (int i = 1; i <= n; i++)
{
int pi, si, ei;
cin >> pi >> si >> ei;
sum += pi; //记录源点流出的最大流量，即每个任务完成所需时间的累加
maxd = max(ei, maxd); //记录最晚的那一天
add(s, i, pi); //超级源点到每个任务的流量为任务所需时间pi
add(i, s, 0); //反悔边
for (int j = si; j <= ei; j++)
{
add(i, j + n, 1); //每个任务和其开始到结束的每一天连起来，容量为1
add(j + n, i, 0); //因为做一天只能算一天的任务，不能一天把pi天的都做完
}
}
int t = maxd + n + 1; //超级汇点
for (int i = n + 1; i < t; i++)
{
add(i, t, m); //每一天到汇点的容量为m
add(t, i, 0); //因为每天只能同时有m个机器工作
}
if (dinic(s, t) == sum) //如果每个任务都干满了pi天，那就说明完成了
cout << "Case " << ++cnt << ": Yes" << endl;
else
cout << "Case " << ++cnt << ": No" << endl;
if (t)
cout << endl;
}
return 0;
} 
OωO
