Task Schedule
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
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.
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
题意:
有n个任务，m台机器。第i个任务，从si天，到ei天内处理pi遍结束。每次机器只能处理一个任务。
问能否完成所有的任务。
思路:
最大流解决。建立超级源点和汇点。源点和每个任务建边，权值为处理的次数pi，表示完成
该任务需要的ci次数。对于每一个任务，若能在si到ei间，那么从第i个任务建边到si到ei天 ，
权值为1，表示每一天能够处理一次。从每一天建边到汇点，权值为机器数量，
表示每天能够处理m个任务。如果汇点得到的值等于源点流出的值，那么yes。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1<<30
#define MOD 1000000007
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pi acos(-1.0)
using namespace std;
const int MAXN = ;
const int MAXM = ;
struct node{
int to;
int val;
int next;
}edge[MAXM*];
int x[MAXN],y[MAXN],z[MAXN];
int pre[MAXN],vis[MAXN],ind,k,n,m,S,T;
void add(int x,int y,int z){
edge[ind].to = y;
edge[ind].val = z;
edge[ind].next = pre[x];
pre[x] = ind ++;
}
bool bfs(){
queue<int>q;
memset(vis,-,sizeof(vis));
vis[S] = ;
q.push(S);
while(!q.empty()){
int tp = q.front();
q.pop();
for(int i = pre[tp]; i != -; i = edge[i].next){
int t = edge[i].to;
if(vis[t] == - && edge[i].val){
vis[t] = vis[tp] + ;
q.push(t);
}
}
}
return vis[T] != -;
}
int dfs(int rt,int low){
int used = ;
if(rt == T){
return low;
}
for(int i = pre[rt]; i != - && used < low; i = edge[i].next){
int t = edge[i].to;
if(vis[t] == vis[rt] + && edge[i].val){
int b = dfs(t,min(low-used,edge[i].val));
edge[i].val -= b;
edge[i^].val += b;
used += b;
}
}
if(used == ){
vis[rt] = -;
}
return used;
}
int main(){
int t,ff = ;
scanf("%d",&t);
while(t--){
scanf("%d%d",&m,&k);
ind = ;
memset(pre,-,sizeof(pre));
n = ;
ll all = ;
for(int i = ; i <= m; i++){
int fx,fy,fz;
scanf("%d%d%d",&fx,&fy,&fz);
x[i] = fy;
y[i] = fx;
z[i] = fz;
n = max(n,z[i]);
all += y[i];
}
for(int i = ; i <= m; i++){
for(int j = x[i]; j <= z[i]; j++){
add(i,j+m,),add(j+m,i,);
}
}
S = ,T = m + n + ;
for(int i = ; i <= m; i++){
add(S,i,y[i]),add(i,S,);
}
for(int i = ; i <= n; i++){
add(i+m,T,k),add(T,i+m,);
}
ll ans = ;
while(bfs()){
while(){
ll a = dfs(S,INF);
if(!a)break;
ans += a;
}
}
//cout<<S<<" "<<T<<endl;
printf("Case %d: ",++ff);
if(ans == all){
printf("Yes\n");
}
else {
printf("No\n");
}
printf("\n");
}
return ;
}