跟着风神学图论Task Schedule(Hdu3572网络流)
题意: 有一个工厂最近新近了一批机器人,这些机器人被用来解决若干个任务.每个任务都有完成所需的时间pi和规定了必须在si天或者si天之后才能处理这个任务,且需要在ei天之内完成. 工厂规定每个机器人每天只能处理一个任务,且每个任务最多只能由一个机器处理. 问这些机器人能否在顺利完成这些任务.
题解: 网络流建模. 对于每一个任务来说,它必须要在si到ei天之间被处理. 并且要在pi天以内完成. 所以我们可以把每一天当成点来考虑,那么每天就有m个机器在工作,相当于每一天有流量为m的物品流向任务区,每个任务也当成点,那么为了保证每个任务每天只能有一个机器人处理,那我们从就可以从天这些点往任务连边,然后每个任务往汇点t流一条流量为pi的边,同理,汇点s往天数连一条流量为m的边.这样就是跑最大流,看最后是不是满流就可以了.
/* ***********************************************Author:xdloveCreated Time :2015年08月18日 星期二 21时48分52秒File Name:a.cpp************************************************ */;const int MAXN = 1100;const int MAXM = 2e6;const int INF = 0x3f3f3f3f;struct Node{int from,to,next;int cap;}edge[MAXM * 2];int tol;int Head[MAXN];int que[MAXN];[MAXN];Init(){tol = 0;memset(Head,-1,sizeof(Head));}void add_edge(int u, int v, int w){edge[tol].from = u;edge[tol].to = v;edge[tol].cap = w;edge[tol].next = Head[u];Head[u] = tol++;edge[tol].from = v;edge[tol].to = u;edge[tol].cap = 0;edge[tol].next = Head[v];Head[v] = tol++;}int BFS(int start, int end){int front, rear;front = rear = 0;memset(dep, -1, sizeof(dep));que[rear++] = start;dep[start] = 0;while (front != rear){int u = que[front++];if (front == MAXN)front = 0;for (int i = Head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (edge[i].cap > 0 && dep[v] == -1){dep[v] = dep[u] + 1;que[rear++] = v;if (rear >= MAXN)rear = 0;if (v == end)return 1;}}}return 0;}int dinic(int start, int end){int res = 0;int top;while (BFS(start, end)){memcpy(cur, Head, sizeof(Head));int u = start;top = 0;while (true){if (u == end){int min = INF;int loc;for (int i = 0; i < top; i++)if (min > edge[stack[i]].cap){min = edge[stack[i]].cap;loc = i;}for (int i = 0; i < top; i++){edge[stack[i]].cap -= min;edge[stack[i] ^ 1].cap += min;}res += min;top = loc;u = edge[stack[top]].from;}for (int i = cur[u]; i != -1; cur[u] = i = edge[i].next)if (edge[i].cap != 0 && dep[u] + 1 == dep[edge[i].to])break;if (cur[u] != -1){stack[top++] = cur[u];u = edge[cur[u]].to;}else{if (top == 0)break;dep[u] = -1;u = edge[stack[–top]].from;}}}return res;}int main(){T,n,m;int cnt = 0;cin>>T;while(T–){scanf(“%d %d”,&n,&m);Init();int s = 0;int t = 1001;int sum = 0;for(int i = 1; i <= n; i++){int p,s,e;scanf(“%d %d %d”,&p,&s,&e);for(int k = s; k <= e; k++)add_edge(k,500 + i,1);add_edge(500 + i,t,p);sum += p;}for(int i = 1; i <= 500; i++)add_edge(s,i,m);int ans = dinic(s,t);printf(“Case %d: “,++cnt);puts(ans == sum ? “Yes” : “No”);puts(“”);}return 0;}
，走马观花之外，这才是深入体验，探索自我的最佳时间，
