hdu 3572 Task Schedule (网络流)

Task Schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3036 Accepted Submission(s): 1086

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

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

2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC

Recommend

zhouzeyong | We have carefully selected several similar problems for you: 3491 1533 3416 3081 3338

构图完成后就是模板题了。

构图：

先建立一个超级源点，然后与每个任务连接，容量为pi。然后每个任务与对应的日期连接，容量为1,。最后天数和一个超级汇点连接，容量为m。

当计算出来的最大流maxflow==sum(pi)时可完成任务，否则不能。

参考： http://blog.csdn.net/luyuncheng/article/details/7944417

代码：

  1 //78MS    2200K    2777 B    G++    
  2 #include<stdio.h>
  3 #include<string.h>
  4 #define N 1005
  5 #define inf 0x7ffffff
  6 struct node{
  7     int v,c,next;
  8 }edge[N*N];
  9 
 10 int head[N],eid;
 11 int gap[N];
 12 int d[N];
 13 int pre[N];
 14 int curnode[N];
 15 int n,m,source,sink,nn;
 16 
 17 void addedge(int u,int v,int c)
 18 {
 19     edge[eid].v=v;
 20     edge[eid].c=c;
 21     edge[eid].next=head[u];
 22     head[u]=eid++;
 23     edge[eid].v=u;
 24     edge[eid].c=0;
 25     edge[eid].next=head[v];
 26     head[v]=eid++;
 27 }
 28 
 29 int ISAP()
 30 {
 31     int flow=0;
 32     memset(d,0,sizeof(d));
 33     memset(gap,0,sizeof(gap));
 34     memset(pre,-1,sizeof(pre));
 35     for(int i=1;i<=nn;i++) curnode[i]=head[i];
 36     gap[nn]=nn;
 37     int v,u=source,neck;
 38     
 39     while(d[source]<nn){
 40                         
 41         if(u==sink){ //找到增广路径 
 42             int tflow=inf;
 43             for(int i=source;i!=sink;i=edge[curnode[i]].v){
 44                 if(tflow>edge[curnode[i]].c){
 45                     neck=i;
 46                     tflow=edge[curnode[i]].c;
 47                 }
 48             }
 49             for(int i=source;i!=sink;i=edge[curnode[i]].v){
 50                 int temp=curnode[i];
 51                 edge[temp].c-=tflow;
 52                 edge[temp^1].c+=tflow;
 53             }
 54             
 55             flow+=tflow;
 56             u=neck;
 57         }
 58         
 59         for(v=curnode[u];v!=-1;v=edge[v].next) //查找允许弧 
 60             if(edge[v].c>0 && d[u]==d[edge[v].v]+1)
 61                 break;
 62                 
 63         if(v!=-1){  //找到允许弧 
 64             curnode[u]=v;
 65             pre[edge[v].v]=u;
 66             u=edge[v].v;
 67             
 68         }else{  //不存在允许弧，回退一步 
 69         
 70             if(--gap[d[u]]==0) break; //断层结束算法 
 71             
 72             curnode[u]=head[u];
 73             int temp=nn;
 74             for(int i=head[u];i!=-1;i=edge[i].next)
 75                 if(edge[i].c>0 && temp>d[edge[i].v])
 76                     temp=d[edge[i].v];
 77             d[u]=temp+1;
 78             ++gap[d[u]];
 79             if(u!=source) u=pre[u];
 80         }
 81     }
 82     
 83     return flow;
 84 }
 85 
 86 int main(void)
 87 {
 88     int t,p,s,e;
 89     int k=1;
 90     scanf("%d",&t);
 91     while(t--)
 92     {
 93         source=0;
 94         scanf("%d%d",&n,&m);
 95         memset(head,-1,sizeof(head));
 96         eid=0;
 97         int sump=0;
 98         int maxn=0;
 99         //构图 
100         for(int i=1;i<=n;i++){
101             scanf("%d%d%d",&p,&s,&e);
102             sump+=p;
103             addedge(source,i,p);
104             for(int j=s;j<=e;j++)
105                 addedge(i,n+j,1);
106             maxn=maxn>e?maxn:e;
107         }
108         sink=n+maxn+1;
109         nn=sink+1;
110         for(int i=1;i<=maxn;i++)
111             addedge(i+n,sink,m);
112         
113         printf("Case %d: ",k++);
114         if(ISAP()==sump) puts("Yes
");
115         else puts("No
");
116     }
117     return 0;
118 }