题目链接：
pid=3572
题意：m台机器。须要做n个任务。
第i个任务。你须要使用机器Pi天，且这个任务要在[Si , Ei]区间内完毕才有效。
对于一个任务，仅仅能由一个机器来完毕。一个机器同一时间仅仅能做一个任务。
当然，一个任务能够分成几段不连续的时间来完毕。问，是否能做完所有任务。
题意非常清晰。也就是推断是否是满流。
对于网络流问题，模板大家都有，关键在于怎样建图（）
思路：今天问了龙哥，对建图有了一定的了解，建图分为4部分，源点->X集合->Y集合->汇点（X、Y类似于二分匹配图）。确定这个4个部分后，就是找这个4个部分的关系，也就是构建容量网络
这题的X集合能够当做任务编号。Y集合当做天数（第几天）
某任务->某一天。若是能够在这天做任务。建一条容量为1的边，最后，把每天到汇点再建一条边容量M（表示每台机器最多工作M个任务）即最大容量是M。
以第二组实例作图（真挫。。）
模板应用的是ISAP（可当做模板）。个人非常倾向ISAP
| Accepted | 2292 KB | 62 ms |
#include#include #include #include #include #include #include #define init(a) memset(a,0,sizeof(a))#define PI acos(-1,0)using namespace std;const int maxn = 1100;const int maxm = 400000;#define lson left, m, id<<1#define rson m+1, right, id<<1|1#define min(a,b) (a>b)?b:a#define max(a,b) (a>b)?a:b#define MAX INT_MAXint head[maxn], sum, bnum;int dis[maxn]; //残量网络中节点 i 到汇点 t 的最短距离int num[maxn]; //和 t 的最短距离等于 i 的节点数量int cur[maxn]; //当前弧下标int pre[maxn]; //可增广路上的上一条弧的编号struct node{ int v, cap; int next;}edge[maxm];void add(int u, int v, int cap)//加边，储存地图{ edge[bnum].v=v; edge[bnum].cap=cap; edge[bnum].next=head[u]; head[u]=bnum++; edge[bnum].v = u; edge[bnum].cap=0; edge[bnum].next=head[v]; head[v] = bnum++;}void BFS(int source,int sink)//预处理。利用反向BFS。更新dis数组{ queue q; while(q.empty()==false) q.pop(); memset(num,0,sizeof(num)); memset(dis,-1,sizeof(dis)); q.push(sink); dis[sink]=0; num[0]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(dis[v] == -1) { dis[v] = dis[u] + 1;//找同意弧 num[dis[v]]++; q.push(v); } } }}int ISAP(int source,int sink,int n)//n为残量网络中的节点到汇点的最大距离，通常节点的个数。即上限{ memcpy(cur,head,sizeof(cur)); int flow=0, u = pre[source] = source; BFS( source,sink);//更新dis数组 while( dis[source] < n ) { if(u == sink) { int df = MAX, pos; for(int i = source;i != sink;i = edge[cur[i]].v)//追踪增广路路径。最小残量df { if(df > edge[cur[i]].cap) { df = edge[cur[i]].cap; pos = i; } } for(int i = source;i != sink;i = edge[cur[i]].v) //更新流量 { edge[cur[i]].cap -= df; edge[cur[i]^1].cap += df; } flow += df; u = pos; } int st; for(st = cur[u];st != -1;st = edge[st].next)// 从当前弧開始查找同意弧 { if(dis[edge[st].v] + 1 == dis[u] && edge[st].cap)//找到同意弧跳出 { break; } } if(st != -1) { cur[u] = st; pre[edge[st].v] = u; u = edge[st].v; } else { if( (--num[dis[u]])==0 ) break;//GAP优化,出现断层结束 int mind = n; for(int id = head[u];id != -1;id = edge[id].next)//retreat操作：更新 dis 数组 { if(mind > dis[edge[id].v] && edge[id].cap) { cur[u] = id;//改动标号的同一时候改动当前弧 mind = dis[edge[id].v]; } } dis[u] = mind+1; num[dis[u]]++; if(u!=source) u = pre[u];// 回溯继续寻找同意弧 } } return flow;}void initt(){ memset(head,-1,sizeof(head)); bnum=0;}int main(){ int T, N,M,a,b,c; int maa, sum, source, sink, n; scanf("%d", &T); for (int cas = 1; cas <= T; ++cas) { initt(); sum = 0; source = 0; maa = 0; scanf("%d%d", &N, &M); for (int i = 1; i <= N; i++) { scanf("%d%d%d", &a, &b, &c); sum += a; if(c > maa) maa = c; add(source, i, a); for (int j = b; j <= c; ++j) { add(i, N + j, 1); } } sink = N + maa + 1; n = sink; for (int i = 1; i <= maa; ++i) { add(N + i, sink, M); } printf("Case %d: ", cas); int ans = ISAP(source, sink, n); if(ans==sum) puts("Yes"); else puts("No"); cout<