国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > HDU 3572 网络流

HDU 3572 网络流

来源:程序员人生   发布时间:2016-07-23 10:27:39 阅读次数:926次

点击打开链接

题意:n个工作,m个机器来完成,每一个工作有P,S,E,P代表这个工作需要P天,而S为最早开始的时间,E为最晚结束时间,每一个机器在固定时间只能做1个工作,问所有的工作能否在规定时间内完成

思路:由于每天的机器只能做1个工作,那末天数肯定是1部,就是2分图的右部,然后左部应当是甚么呢,那就是n个工作了,然后流量,对每一个工作来讲,它需要的天数就是源点到工作的流量,然后工作到右部的就是可以连的就是1,最后的m天呢,我之前是想着直接右部是m个机器的天数,发现太笨拙了,世界在每一个天数后面连向汇点的时候直接是m和之前就是1样的嘛

#include <queue> #include <vector> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3fll; const int maxn=1010; struct edge{ int to,cap,rev; edge(int a,int b,int c){to=a;cap=b;rev=c;} }; vector<edge>G[maxn]; int level[maxn],iter[maxn]; void add_edge(int from,int to,int cap){ G[from].push_back(edge(to,cap,G[to].size())); G[to].push_back(edge(from,0,G[from].size()⑴)); } void bfs(int s){ memset(level,⑴,sizeof(level)); queue<int>que;level[s]=0; que.push(s); while(!que.empty()){ int v=que.front();que.pop(); for(unsigned int i=0;i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } } } int dfs(int v,int t,int f){ if(v==t) return f; for(int &i=iter[v];i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[v]<level[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; while(1){ bfs(s); if(level[t]<0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,inf))>0) flow+=f; } } int P[maxn],E[maxn],S[maxn]; int main(){ int T,n,m,cas=1; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<maxn;i++) G[i].clear(); int max1=0,sum=0; for(int i=1;i<=n;i++){ scanf("%d%d%d",&P[i],&S[i],&E[i]); sum+=P[i]; if(E[i]>max1) max1=E[i]; } for(int i=1;i<=n;i++) add_edge(0,i,P[i]); for(int i=1;i<=n;i++){ for(int j=S[i];j<=E[i];j++){ add_edge(i,j+n,1); } } for(int i=1;i<=max1;i++) add_edge(i+n,n+max1+1,m); int ans=max_flow(0,n+max1+1); if(ans==sum) printf("Case %d: Yes\n",cas++); else printf("Case %d: No\n",cas++); printf("\n"); } return 0; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生