Task ScheduleTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5007Accepted Submission(s): 1636
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
24 31 3 5 1 1 42 3 73 5 92 22 1 31 2 2
Sample Output
Case 1: YesCase 2: Yes
Author
allenlowesy
Source
2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC
题意：有M个机器，，有N个任务。每个任务必须在Si 或者以后开始做，在Ei 或者之前完成，完成任务必须处理Pi 个时间单位。其中，每个任务可以在任意（空闲）机器上工作，每个机器的同一时刻只能工作一个任务，每个任务在同一时刻只能被一个机器工作，而且任务做到一半可以打断，拿去其他机器做。问：能否在规定时间内把任务做完。
思路：建图是关键，我们可以选择0为源点，然后源点与每个任务都连一条边，容量为要求的天数p,然后每个任务都与相应的时间点连边，边容量为1，最后我们要确定汇点，汇点可以取vt=maxtime+n+1(其中maxtime为结束时间的最大值，n为任务数），这样确定好汇点之后，再在每个时间点与汇点之间连边，边容量为m,为机器数(表示每个时间点最多可以有m台机器处理任务)，最后判断sum(for all pi)==?SAP即可。
#include<stdio.h>#include<string.h>#include<queue>using namespace std;#define captype intconst int MAXN = 1010; //点的总数const int MAXM = 520010; //边的总数const int INF = 1<<30;struct EDG{int to,next;captype cap,flow;} edg[MAXM];int eid,head[MAXN];int gap[MAXN]; //每种距离(或可认为是高度)点的个数int dis[MAXN]; //每个点到终点eNode 的最短距离int cur[MAXN]; //cur[u] 表示从u点出发可流经 cur[u] 号边void init(){eid=0;memset(head,-1,sizeof(head));}//有向边 三个参数，无向边4个参数void addEdg(int u,int v,captype c,captype rc=0){edg[eid].to=v; edg[eid].next=head[u];edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;edg[eid].to=u; edg[eid].next=head[v];edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;}//预处理eNode点到所有点的最短距离void BFS(int sNode, int eNode){queue<int>q;memset(gap,0,sizeof(gap));memset(dis,-1,sizeof(dis));gap[0]=1;dis[eNode]=0;q.push(eNode);while(!q.empty()){int u=q.front(); q.pop();for(int i=head[u]; i!=-1; i=edg[i].next){int v=edg[i].to;if(dis[v]==-1){dis[v]=dis[u]+1;gap[dis[v]]++;q.push(v);}}}}int S[MAXN]; //路径栈，存的是边的id号captype maxFlow_sap(int sNode,int eNode, int n){BFS(sNode, eNode);//预处理eNode到所有点的最短距离if(dis[sNode]==-1) return 0; //源点到不可到达汇点memcpy(cur,head,sizeof(head));int top=0; //栈顶captype ans=0; //最大流int u=sNode;while(dis[sNode]<n){ //判断从sNode点有没有流向下一个相邻的点if(u==eNode){ //找到一条可增流的路captype Min=INF ;int inser;for(int i=0; i<top; i++) //从这条可增流的路找到最多可增的流量Minif(Min>edg[S[i]].cap-edg[S[i]].flow){Min=edg[S[i]].cap-edg[S[i]].flow;inser=i;}for(int i=0; i<top; i++){edg[S[i]].flow+=Min;edg[S[i]^1].flow-=Min; //可回流的边的流量}ans+=Min;top=inser; //从这条可增流的路中的流量瓶颈 边的上一条边那里是可以再增流的，所以只从断流量瓶颈 边裁断u=edg[S[top]^1].to; //流量瓶颈 边的起始点continue;}bool flag = false; //判断能否从u点出发可往相邻点流int v;for(int i=cur[u]; i!=-1; i=edg[i].next){v=edg[i].to;if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){flag=true;cur[u]=i;break;}}if(flag){S[top++] = cur[u]; //加入一条边u=v;continue;}//如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1int Mind= n;for(int i=head[u]; i!=-1; i=edg[i].next)if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){Mind=dis[edg[i].to];cur[u]=i;}gap[dis[u]]–;if(gap[dis[u]]==0) return ans; //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径//因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1gap[dis[u]]++;if(u!=sNode) u=edg[S[–top]^1].to; //退一条边}return ans;}int main(){int T,cas=0,n,m;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);init();int maxtime=0,sump=0;for(int i = 1; i<=n; i++){int P,S,E;scanf("%d%d%d",&P,&S,&E);sump += P; //总流量if(E>maxtime)maxtime = E;addEdg(0,i,P); //源点0到任务i的最大流量为Pfor(int j=S; j<=E; j++)addEdg(i,n+j,1); //任务i到时间点j+n，边最大容量为1}int t=maxtime + n +1;for(int j=1; j<=maxtime; j++)addEdg(j+n,t,m);<span style="white-space:pre"></span>//每个时间点到汇点t，边最大容量为mprintf("Case %d: %s\n\n",++cas,maxFlow_sap(0,t,t)==sump?"Yes":"No");}}
一定要成为你工作最大的资产。
