题意：给出v种机器，m个任务，给出每一个任务完成需要的时间p天，要在s-e时间段内完成，问可不可以完成（任务可以不连续完成）
思路：这个题确实很不好想，0点作为源点S，1001为汇点T，往下看。
1-500作为每个任务的点，S向第i个点连边，权值为p。501-1000作为每一天的情况。第i个任务的完成的区间是s-e,那么就从i点向s+5000-e+5000区间的所有点都连接一个权值为1的点。501-1000的每一天向汇点T连接一个边，权值为v。(v是机器的个数，表示一天最多可以处理多少个任务)然后跑dinic就行了链接：http://acm.hdu.edu.cn/showproblem.php?pid=3572
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf 0x3f3f3f3f const int maxn1=1e5+5; int ans=2,head[maxn1],deep[maxn1],n[maxn1],N,M,S,T,V,vis[maxn1],cur[maxn1]; struct edge{ int to,next,v; }e[(int)(2e6)]; void add(int x,int y,int v){ e[ans].to=y,e[ans].next=head[x],e[ans].v=v,head[x]=ans++; } bool bfs(){ memset(deep,0,sizeof(deep)); for(int i=0;i<=1001;i++) cur[i]=head[i]; int l=1,r=1; deep[S]=1; n[1]=S; while(l<=r){ int x=n[l]; for(int i=head[x];i;i=e[i].next){ int y=e[i].to,v=e[i].v; if(!deep[y]&&v){//易忽略边不为0 deep[y]=deep[x]+1; n[++r]=y; } } l++; } if(deep[T]) return true; else return false; } int dfs(int x,int dist) { if(x==T||0==dist) return dist; int res=0,tp; for(int i=cur[x];i;i=e[i].next){ cur[x]=i; int y=e[i].to; if(deep[y]==deep[x]+1&&e[i].v){//易忽略边不为0 tp=dfs(y,min(dist,e[i].v)); e[i].v-=tp; e[i^1].v+=tp; res+=tp; dist-=tp; if(0==dist) break; } } if(!res) deep[x]=0;//这个优化真是。。。加上效果太明显了 return res; } void init(){ memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); ans=2; } int main() { S=0,T=1001; int t,Case=1; scanf("%d",&t); while(t--){ scanf("%d%d",&M,&V); init(); int sum1=0,sum2=0; for(int i=1,a,b,v;i<=M;i++){ scanf("%d%d%d",&v,&a,&b); sum1+=v; add(0,i,v); add(i,0,0); for(int j=a;j<=b;j++){ add(i,j+500,1); add(j+500,i,0); vis[j+500]=1; } } for(int i=501;i<=1000;i++){ if(vis[i]){ add(i,T,V); add(T,i,0); } } while(bfs()) sum2+=dfs(S,inf); printf("Case %d: ",Case++); if(sum1==sum2) printf("Yes\n\n"); else printf("No\n\n"); } return 0; }
