首页 > 代码库 > HDU 3572 Task Schedule（最大流判断满流）
HDU 3572 Task Schedule（最大流判断满流）
https://vjudge.net/problem/HDU-3572
题意：
有N个作业和M台机器，每个作业都有一个持续时间P，工作的日期为S~E。作业可以断断续续的在不同机器上做，每台机器每次只可以处理一个作业。判断是否可以在作业的工作日期内完成所有作业。
思路：
建立源点0和汇点t，因为天数最多为500，所有我们将日期的编号定为1~500，作业的编号为500+i。
对于每个作业，与源点0相连，容量为P，意味着它必须走完这P容量才能完成这作业。与S~E相连，容量为1。日期与汇点相连，容量为m，说明每天能处理m个作业。
最后计算出最大流，如果等于所有作业的P之和，说明是可以完成的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 8 const int maxn=1000+5; 9 const int INF=0x3f3f3f3f; 10 11 int n,m; 12 int ans; 13 14 struct Edge 15 { 16 int from,to,cap,flow; 17 Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){} 18 }; 19 20 struct Dinic 21 { 22 int n,m,s,t; 23 vector<Edge> edges; 24 vector<int> G[maxn]; 25 bool vis[maxn]; 26 int cur[maxn]; 27 int d[maxn]; 28 29 void init(int n) 30 { 31 this->n=n; 32 for(int i=0;i<n;++i) G[i].clear(); 33 edges.clear(); 34 } 35 36 void AddEdge(int from,int to,int cap) 37 { 38 edges.push_back( Edge(from,to,cap,0) ); 39 edges.push_back( Edge(to,from,0,0) ); 40 m=edges.size(); 41 G[from].push_back(m-2); 42 G[to].push_back(m-1); 43 } 44 45 bool BFS() 46 { 47 queue<int> Q; 48 memset(vis,0,sizeof(vis)); 49 vis[s]=true; 50 d[s]=0; 51 Q.push(s); 52 while(!Q.empty()) 53 { 54 int x=Q.front(); Q.pop(); 55 for(int i=0;i<G[x].size();++i) 56 { 57 Edge& e=edges[G[x][i]]; 58 if(!vis[e.to] && e.cap>e.flow) 59 { 60 vis[e.to]=true; 61 d[e.to]=d[x]+1; 62 Q.push(e.to); 63 } 64 } 65 } 66 return vis[t]; 67 } 68 69 int DFS(int x,int a) 70 { 71 if(x==t || a==0) return a; 72 int flow=0, f; 73 for(int &i=cur[x];i<G[x].size();++i) 74 { 75 Edge &e=edges[G[x][i]]; 76 if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0) 77 { 78 e.flow +=f; 79 edges[G[x][i]^1].flow -=f; 80 flow +=f; 81 a -=f; 82 if(a==0) break; 83 } 84 } 85 return flow; 86 } 87 88 int Maxflow(int s,int t) 89 { 90 this->s=s; 91 this->t=t; 92 int flow=0; 93 while(BFS()) 94 { 95 memset(cur,0,sizeof(cur)); 96 flow +=DFS(s,INF); 97 } 98 return flow; 99 }100 }DC;101 102 int main()103 {104 //freopen("D:\\input.txt","r",stdin);105 int T;106 int kase=0;107 scanf("%d",&T);108 while(T--)109 {110 scanf("%d%d",&n,&m);111 ans=0;112 DC.init(500+2+n);113 114 bool vis[maxn];//表示第i天是否被用到115 memset(vis,0,sizeof(vis));116 117 for(int i=1;i<=n;++i)118 {119 int P,S,E;120 scanf("%d%d%d",&P,&S,&E);121 DC.AddEdge(0,500+i,P);122 ans += P;123 for(int j=S;j<=E;++j)124 {125 DC.AddEdge(500+i,j,1);126 vis[j]=true;127 }128 }129 130 for(int i=1;i<=500;++i)if(vis[i])//被任务覆盖的日子才添加131 DC.AddEdge(i,500+n+1,m);132 printf("Case %d: %s\n\n",++kase,DC.Maxflow(0,500+n+1)==ans?"Yes":"No");133 }134 return 0;135 }
HDU 3572 Task Schedule（最大流判断满流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。