首页 > 代码库 > HDU 3572 Task Schedule
HDU 3572 Task Schedule
http://acm.hdu.edu.cn/showproblem.php?pid=3572
题意:给N个任务,M台机器。每个任务有最早才能开始做的时间S,deadline E,和持续工作的时间P。问存不存在可行的工作时间。
题解:最大流。主要问题在于建模……
建模:源点与每一个任务建边,容量为P;每一天与汇点建边,容量为M;每一个任务和天数建边,容量为1。
判断:判断最后求得最大流是否和所有任务处理的次数之和相等,如果相等就输出Yes。
第一次写ISP,以后做模板用了……
1 #include <iostream> 2 using namespace std; 3 4 const int INF=0xfffffff; 5 const int maxn=1010; 6 const int maxm=500010; 7 8 struct edge{ 9 int v,next,val; 10 } G[maxm]; 11 int pre[maxn],idx, sum; 12 int N,M; 13 int level[maxn]; 14 int gap[maxn]; 15 int s,t; 16 17 void add_edge(int from,int to,int val) 18 { 19 G[idx].v=to; 20 G[idx].val=val; 21 G[idx].next=pre[from]; 22 pre[from]=idx++; 23 24 G[idx].v=from; 25 G[idx].val=0; 26 G[idx].next=pre[to]; 27 pre[to]=idx++; 28 } 29 30 int dfs(int pos,int cost, int cnt) 31 { 32 if (pos==t) 33 { 34 return cost; 35 } 36 37 int j,minh=cnt-1,lv=cost,d; 38 39 for (j=pre[pos];j!=-1;j=G[j].next) 40 { 41 int v=G[j].v,val=G[j].val; 42 if(val>0) 43 { 44 if (level[v]+1==level[pos]) 45 { 46 if (lv<G[j].val) d=lv; 47 else d=G[j].val; 48 49 d=dfs(v,d,cnt); 50 G[j].val-=d; 51 G[j^1].val+=d; 52 lv-=d; 53 if (level[s]>=cnt) return cost-lv; 54 if (lv==0) break; 55 } 56 57 if (level[v]<minh) minh=level[v]; 58 } 59 } 60 61 if (lv==cost) 62 { 63 --gap[level[pos]]; 64 if (gap[level[pos]]==0) level[s]=cnt; 65 level[pos]=minh+1; 66 ++gap[level[pos]]; 67 } 68 69 return cost-lv; 70 71 } 72 73 int sap(int s,int t, int cnt) 74 { 75 int flow=0; 76 gap[s]=cnt; 77 while (level[s]<cnt) 78 { 79 flow+=dfs(s,INF, cnt); 80 } 81 82 return flow; 83 } 84 85 void init() 86 { 87 memset(pre, -1, sizeof(pre)); 88 memset(gap,0,sizeof(gap)); 89 memset(level,0,sizeof(level)); 90 sum = idx = 0; 91 } 92 93 int main() 94 { 95 //freopen("/Users/apple/Desktop/暑假/24.1/24.1/in","r",stdin); 96 int T, ca = 1; 97 scanf("%d", &T); 98 while (T--) 99 {100 init();101 scanf("%d %d", &N, &M);102 int P, S, E;103 int mint=INF;104 int maxt=-1;105 for (int i = 1; i <= N; ++i)106 {107 scanf("%d %d %d", &P, &S, &E);108 sum += P;109 if(mint>S) mint=S;110 if(maxt<E) maxt=E;111 add_edge(0, i, P);112 for (int j = S; j <= E; ++j)113 {114 add_edge(i, N+j, 1);115 }116 }117 int days=maxt-mint+1;118 s=0;119 t=N+days+1;120 for (int i = 1; i <= days; ++i)121 {122 add_edge(i+N, N+days+1, M);123 }124 125 printf("Case %d: ",ca++);126 int flow1=sap(s,t,t+1);127 if(flow1==sum){128 puts("Yes");129 puts("");130 }131 else{132 puts("No");133 puts("");134 }135 }136 return 0;137 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。