Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 3036 Accepted
Submission(s): 1086
构图完成后就是模板题了。
构图:
先建立一个超级源点,然后与每个任务连接,容量为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\n"); 115 else puts("No\n"); 116 } 117 return 0; 118 }
hdu 3572 Task Schedule (网络流),布布扣,bubuko.com
原文:http://www.cnblogs.com/GO-NO-1/p/3722001.html