HDU 3572 网络流
题意：
n个任务， m台机器(每台机器每天只能执行一个任务) 任务可以不连续执行，可以让别的机器交替执行
下面n行
need st en 表示任务需要在 [st, en]之间完成，需要need天 (保证 en - st+1 >=need )
问能否全部执行完
思路：
0为源点，1-n为n个任务 (源点到天数边权值为 need)
n+1 - n+1+Maxday 为天数
每个任务到 [st, en]建权值为1的边
每个任务到汇点建权值为m的边
#include<string.h>#include<stdio.h>#include<queue>#define M 1505#define inf 33554432using namespace std;inline int Max(int a,int b){return a<b?b:a;}inline int Min(int a,int b){return a>b?b:a;}struct Edge{ int from, to, cap, nex;}edge[M*M];int head[M*4], edgenum;void addedge(int u, int v, int cap){ Edge E = { u, v, cap, head[u]}; edge[ edgenum ] = E; head[u] = edgenum ++;}int sign[M*4], s, t;bool BFS(int from, int to){ memset(sign, -1, sizeof(sign)); sign[from] = 0; queue<int>q; q.push(from); while( !q.empty() ){ int u = q.front(); q.pop(); for(int i = head[u]; i!=-1; i = edge[i].nex) { int v = edge[i].to; if(sign[v]==-1 && edge[i].cap) { sign[v] = sign[u] + 1, q.push(v); if(sign[to] != -1)return true; } } } return false;}int Stack[M*4], top, cur[M*4];int day;int dinic(){ int ans = 0; while( BFS(s, t) ) { memcpy(cur, head, sizeof(head)); int u = s; top = 0; while(1) { if(u == t) { int flow = inf, loc;//loc 表示 Stack 中 cap 最小的边 for(int i = 0; i < top; i++) if(flow > edge[ Stack[i] ].cap) { flow = edge[Stack[i]].cap; loc = i; } for(int i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from; } for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标 if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[ cur[u] ].to; } else { if( top == 0 )break; sign[u] = -1; u = edge[ Stack[--top] ].from; } } } return ans == day;}void Have_map(int n, int m){ day = 0; memset(head, -1, sizeof(head)); edgenum = 0; int i, j; int st, need, en, Maxday = 1; for(i = 1; i <= n; i++) { scanf("%d %d %d",&need,&st,&en); addedge(s, i, need); addedge(i, s, 0 ); day += need; for(j = st; j <= en; j++) { addedge(i, n + 1 + j, 1); addedge(n + 1 + j, i, 0); } Maxday = Max(Maxday, en); } t = n + Maxday + 10; for(i = 1; i <= Maxday; i++) { addedge(n+i+1, t, m); addedge(t, n+i+1, 0); }}int main(){ int n, m, T, Cas = 1;scanf("%d",&T); s = 0; while(T--) { scanf("%d %d", &n, &m); Have_map(n, m); printf("Case %d: ",Cas++); if(dinic()) printf("Yes\n\n"); else printf("No\n\n"); } return 0;}