pid=3572">Task Schedule
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3412 Accepted Submission(s): 1197
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.
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
思路：建一个超级源点0，然后如果工作区间长度为T ,再建立[1，T]个点，源点到每一个点的流量为M（每天仅仅有M台机器工作）。接着。把对应的工作日向后平移T 天，每一个工作日到对应的[1,T]的流量为1，到终点的流量也为1.
最后求最大流是否大于等于总总工作量就是了。
#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
#define N 1005
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
const int inf=0x7ffffff;
int cnt,n,m,t;
int head[N],q[N],dis[N];
struct node
{
int u,v,w,next;
}map[N*N];
void add(int u,int v,int w)
{
map[cnt].u=u;
map[cnt].v=v;
map[cnt].w=w;
map[cnt].next=head[u];
head[u]=cnt++;
map[cnt].u=v;
map[cnt].v=u;
map[cnt].w=0;
map[cnt].next=head[v];
head[v]=cnt++;
}
int bfs()
{
int i,u,v,t1,t2;
memset(dis,0,sizeof(dis));
u=t1=t2=0;
dis[u]=1;
q[t1++]=u;
while(t2<t1)
{
u=q[t2++];
for(i=head[u];i!=-1;i=map[i].next)
{
v=map[i].v;
if(map[i].w&&!dis[v])
{
dis[v]=dis[u]+1;
if(v==t)
return 1;
q[t1++]=v;
}
}
}
return 0;
}
int dfs(int s,int lim)
{
int i,tmp,v,cost=0;
if(s==t)
return lim;
for(i=head[s];i!=-1;i=map[i].next)
{
v=map[i].v;
if(map[i].w&&dis[s]==dis[v]-1)
{
tmp=dfs(v,min(lim-cost,map[i].w));
if(tmp>0)
{
map[i].w-=tmp;
map[i^1].w+=tmp;
cost+=tmp;
if(cost==lim)
break;
}
else
dis[v]=-1;
}
}
return cost;
}
int dinic()
{
int ans=0,s=0;
while(bfs())
ans+=dfs(s,inf); //printf("%d\n",ans);
return ans;
}
int main()
{
int i,j,T,sum,t1,t2,cas=1;
int s[505],e[505],p[505];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
t1=N;t2=0;
sum=0;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&p[i],&s[i],&e[i]);
t1=min(t1,s[i]);
t2=max(t2,e[i]);
sum+=p[i];
}
cnt=0;
memset(head,-1,sizeof(head));
for(i=t1;i<=t2;i++) //超级源点到一般源点的流量
{
add(0,i,m);
}
for(i=1;i<=n;i++)
{
for(j=s[i];j<=e[i];j++)
{
add(j,j+t2,1);
add(j+t2,2*t2,1);
}
}
t=t2*2;
if(sum<=dinic())
printf("Case %d: Yes\n\n",cas++);
else
printf("Case %d: No\n\n",cas++);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。