http://acm.hdu.edu.cn/showproblem.php?pid=3572

題意：給N個任務(wù)，M臺機器。每個任務(wù)有最早才能開始做的時間S，deadline E，和持續(xù)工作的時間P。每個任務(wù)可以分段進行,但是在同一時刻,一臺機器最多只能執(zhí)行一個任務(wù). 問存不存在可行的工作時間。

題解：網(wǎng)絡(luò)流+最大流

由于時間<=500且每個任務(wù)都能斷斷續(xù)續(xù)的執(zhí)行,那么我們把每一天時間作為一個節(jié)點來用網(wǎng)絡(luò)流解決該題.

???????建圖: 源點s(編號0), 時間1-500天編號為1到500, N個任務(wù)編號為500+1 到500+N, 匯點t(編號501+N).

???????源點s到每個任務(wù)i有邊(s, i, Pi)

???????每一天到匯點有邊(j, t, M) (其實這里的每一天不一定真要從1到500,只需要取那些被每個任務(wù)覆蓋的每一天即可)

???????如果任務(wù)i能在第j天進行,那么有邊(i, j, 1) 注意由于一個任務(wù)在一天最多只有1臺機器執(zhí)行,所以該邊容量為1,不能為INF或M哦.

最后看最大流是否 == 所有任務(wù)所需要的總天數(shù).

C++版本一

題解：Dinic算法+當(dāng)前弧優(yōu)化

當(dāng)前弧優(yōu)化：因為每次dfs找增廣路的過程中都是從每個頂點指向的第1(編號為0)條邊開始遍歷的，而如果第1條邊已達到滿流，則會繼續(xù)遍歷第2條邊....直至找到匯點，事實上這個遞歸的過程就造成了很多不必要浪費的時間，所以在dfs的過程中應(yīng)標(biāo)記一下每個頂點v當(dāng)前能到達的第curfir[v]條邊，說明頂點v的第0條邊～第curfir[v]-1條邊都已達滿流或者流不到匯點，這樣時間復(fù)雜度就大大降低了。注意：每次bfs給圖重新分層次時，需要清空當(dāng)前弧數(shù)組cirfir[]，表示初始時從每個頂點v的第1(編號為0)條邊開始遍歷。

/* *@Author: STZG *@Language: C++ */#include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> #include<ctime> //#define DEBUG #define RI register int #define endl '\n' using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int s,t,n,m,k,p,l,r,u,v,w,c2; int ans,cnt,flag,temp,sum; int dis[N],cur[N]; struct node{int u,v,c;node(){};node(int form,int to,int cap):u(form),v(to),c(cap){} }; vector<node>edge; vector<int> G[N]; void Addedge(int u,int v,int cap){edge.push_back({u,v,cap});edge.push_back({v,u,0});int sz=edge.size();G[u].push_back(sz-2);G[v].push_back(sz-1); } bool bfs(int u){memset(dis,-1,sizeof(dis));dis[u]=0;queue<int>q;q.push(u);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<G[u].size();i++){node e=edge[G[u][i]];//cout<<u<<" "<<e.v<<endl;if(dis[e.v]<0&&e.c>0){dis[e.v]=dis[u]+1;q.push(e.v);}}}return dis[t]>0; } int dfs(int u,int flow){if(u==t)return flow;int now;for(int &i=cur[u];i<G[u].size();i++){node e=edge[G[u][i]];if(e.c>0&&dis[u]+1==dis[e.v]&&(now=dfs(e.v,min(flow,e.c)))){edge[G[u][i]].c-=now;edge[G[u][i]^1].c+=now;return now;}}return 0; } void dinic(){while(bfs(s)){int res=0;memset(cur,0,sizeof(cur));while(res=dfs(s,INF)){ans+=res;}} } void init(){s=0;t=n+500+1;for(int i=s;i<=t;i++)G[i].clear();edge.clear();ans=0;sum=0; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&k);int T=0;while(k--){scanf("%d%d",&n,&m);init();for(int i=1;i<=500;i++)Addedge(i+n,t,m);for(int i=1;i<=n;i++){scanf("%d%d%d",&p,&u,&v);Addedge(s,i,p);sum+=p;for(int j=u;j<=v;j++)Addedge(i,j+n,1);}dinic();//cout<<ans<<endl;cout<<"Case "<<++T<<": "<<(ans==sum?"Yes":"No")<<endl;cout<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二?

題解：ISAP算法

?

#include<iostream> #include<cmath> #include<cstring> using namespace std; #define MAXN 500 #define MAXE 500002 #define INF 0x7ffffff int ne,nv,tmp,s,t,index; struct Edge{ int next,pair; int v,cap,fLow; }edge[MAXE]; int net[MAXN]; int maxday; int ISAP() { int numb[MAXN],dist[MAXN],curedge[MAXN],pre[MAXN]; int cur_fLow,max_fLow,u,tmp,neck,i; memset(dist,0,sizeof(dist)); memset(numb,0,sizeof(numb)); memset(pre,-1,sizeof(pre)); for(i = 1 ; i <= nv ; ++i) curedge[i] = net[i]; numb[nv] = nv; max_fLow = 0; u = s; while(dist[s] < nv) { if(u == t) { cur_fLow = INF; for(i = s; i != t;i = edge[curedge[i]].v) { if(cur_fLow > edge[curedge[i]].cap) { neck = i; cur_fLow = edge[curedge[i]].cap; } } for(i = s; i != t; i = edge[curedge[i]].v) { tmp = curedge[i]; edge[tmp].cap -= cur_fLow; edge[tmp].fLow += cur_fLow; tmp = edge[tmp].pair; edge[tmp].cap += cur_fLow; edge[tmp].fLow -= cur_fLow; } max_fLow += cur_fLow; u = neck; } /* if .... eLse ... */for(i = curedge[u]; i != -1; i = edge[i].next) if(edge[i].cap > 0 && dist[u] == dist[edge[i].v]+1) break; if(i != -1) { curedge[u] = i; pre[edge[i].v] = u; u = edge[i].v; }else{ if(0 == --numb[dist[u]]) break; curedge[u] = net[u]; for(tmp = nv,i = net[u]; i != -1; i = edge[i].next) if(edge[i].cap > 0) tmp = tmp<dist[edge[i].v]?tmp:dist[edge[i].v]; dist[u] = tmp + 1; ++numb[dist[u]]; if(u != s) u = pre[u]; } } return max_fLow; } void addedge(int u,int v,int f) {edge[index].next = net[u]; edge[index].v = v; edge[index].cap = f; edge[index].fLow = 0; edge[index].pair = index+1; net[u] = index++; edge[index].next = net[v]; edge[index].v = u; edge[index].cap = 0; edge[index].fLow = 0; edge[index].pair = index-1; net[v] = index++;} int main() { int i,j,np,nc,m,n; int a,b,d,k,vaL;int tt;scanf("%d",&tt);for(int cas=1;cas<=tt;++cas){ int cases=1;int maxval=0;maxday=0;scanf("%d%d",&n,&m); index=0;//index從0開始掃 s = 0; t = 0; memset(net,-1,sizeof(net)); for(i=1;i<=n;i++){int pi,si,ei;scanf("%d%d%d",&pi,&si,&ei);maxday=max(maxday,ei);maxval+=pi;addedge(s,i,pi);for(j=si;j<=ei;j++)addedge(i,n+j,1);}t=n+maxday+1;nv=t+1;for(i=1;i<=maxday;i++)addedge(i+n,t,m); int ans=ISAP();if (ans == maxval) printf("Case %d: Yes\n\n", cas); else printf("Case %d: No\n\n", cas); } return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Task Schedule的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。