Task Schedule
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1911 Accepted Submission(s): 687
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.
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
Recommend
zhouzeyong
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=1010; const int EM=500010; const int INF=0x3f3f3f3f; int n,m,cnt,head[VM]; int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM]; //dep表示每个点的距离标记,gap表示距离为i的点有多少个,cur用于当前孤优化, //aug记录找到的增广路流量,path记录找到的增广路的路径。 struct Edge{ int u,v,nxt; int cap; }edge[EM]; void addedge(int cu,int cv,int cw){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].u=cv; edge[cnt].v=cu; edge[cnt].cap=0; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; int SAP(){ int max_flow=0,u=src,v; int id,mindep; aug[src]=INF; pre[src]=-1; memset(dep,0,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=n; for(int i=0;i<=n;i++) cur[i]=head[i]; // 初始化当前弧为第一条弧 while(dep[src]<n){ int flag=0; if(u==des){ max_flow+=aug[des]; for(v=pre[des];v!=-1;v=pre[v]){ // 路径回溯更新残留网络 id=cur[v]; edge[id].cap-=aug[des]; edge[id^1].cap+=aug[des]; aug[v]-=aug[des]; // 修改可增广量,以后会用到 if(edge[id].cap==0) // 不回退到源点,仅回退到容量为0的弧的弧尾 u=v; } } for(int i=cur[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; // 从当前弧开始查找允许弧 if(edge[i].cap>0 && dep[u]==dep[v]+1){ // 找到允许弧 flag=1; pre[v]=u; cur[u]=i; aug[v]=min(aug[u],edge[i].cap); u=v; break; } } if(!flag){ if(--gap[dep[u]]==0) /* gap优化,层次树出现断层则结束算法 */ break; mindep=n; cur[u]=head[u]; for(int i=head[u];i!=-1;i=edge[i].nxt){ v=edge[i].v; if(edge[i].cap>0 && dep[v]<mindep){ mindep=dep[v]; cur[u]=i; // 修改标号的同时修改当前弧 } } dep[u]=mindep+1; gap[dep[u]]++; if(u!=src) // 回溯继续寻找允许弧 u=pre[u]; } } return max_flow; } int main(){ //freopen("input.txt","r",stdin); int t,cases=0; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); cnt=0; memset(head,-1,sizeof(head)); src=0; int sum=0,MAX=0,p,s,e; for(int i=1;i<=n;i++){ scanf("%d%d%d",&p,&s,&e); sum+=p; MAX=max(MAX,e); addedge(src,i,p); //源点与每个任务之间连一条边,容量为完成该任务所需处理次数 for(int j=s;j<=e;j++) //若第i个任务可以在Si至Ei天处理,则由该任务向这些天分别连一条边,容量为1,表示此任务每天只能被处理一次 addedge(i,n+j,1); } des=n+MAX+1; for(int i=1;i<=MAX;i++) addedge(n+i,des,m); //从每一天连一条到汇点的边,容量为机器数M,表示每天可以处理M个任务 n=des+1; if(SAP()==sum) //若求出的最大流等于所有任务需要处理的次数之和,说明能完成任务 printf("Case %d: Yes\n\n",++cases); else printf("Case %d: No\n\n",++cases); } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码