【题意】：
有一个烤箱，烤箱在一个时刻最多考M个肉串，N个顾客，每个顾客有属性s,n,e,t s是来的时间，n是想要的肉串数量，e是最晚离开的时间，t是烤的时间(几分熟)。
顾客的烤肉可以分开烤，比如一串烤肉烤的时间是t，那么分成t分就可以在1的时间内烤完。问能否满足所有的顾客。
很像HDU3527
【思路】：
以时间作为流
每个单位时间只能烤M个肉，那么如果一个顾客的属性为s, n, e, t，那么如果满足n*t <= (t-s)*M则这个顾客是可以被满足的。
那么问题可以转换成区间覆盖问题：线段上每个单位容量为M，每个顾客的区间为[s, e]，顾客容量为n*t，问能否覆盖完全。
【建图】：
类似HDU3527
设立超级源点sp = 0，sp向每个顾客i连边，权重为n*t，每个单位时间向超级汇点tp连边，权重为M，顾客向时间点连边，权重为 inf，跑最大流即可。
！！但是注意到s，e的范围是1e6那么这样直接连边的话内存需要1e8，肯定会MLE，所以要进行离散化。
【离散化】：
使用C++ STL unique( array.begin(), array.end() )函数，将时间点s,e进行排序去重，最多可以获得2*N个时间点，2*N-1个区间，遍历每个时间区间j, [l ,r]时
遍历每个顾客i的时间[s, e]如果s<=l && e>=r 则i->j连边，权重为inf。
最后跑最大流，判断是否满流即可。
#include <bits/stdc++.h> using namespace std; const int maxn = 200 + 5; const int maxm = 1e6 + 5; const int inf = 0x3f3f3f3f; int n, m, sp, tp, sum, maxflow; int s[maxn], e[maxn], Time[maxn<<1], d[maxn*3]; int head[maxn*3], tot; struct edge{ int to, w, next; } ed[maxm<<1]; inline void init(){ sum = sp = 0; tot = 1; memset( head ,-1, sizeof(head) ); } inline void add( int u, int v, int w ){ ed[++tot].to = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot; ed[++tot].to = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot; } inline bool bfs(){ queue<int> q; memset( d, 0, sizeof(d) ); d[sp] = 1; q.push(sp); while( !q.empty() ){ int x = q.front(); q.pop(); for( int i=head[x]; i!=-1; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w && !d[y] ){ d[y] = d[x] + 1; q.push(y); if( y==tp ) return 1; } } } return 0; } inline int dfs( int x, int flow ){ if( x==tp ) return flow; int res = flow, k; for( int i=head[x]; i!=-1 && res; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w && d[y]==d[x]+1 ){ k = dfs( y, min(ed[i].w, res) ); if( !k ) d[y] = 0; ed[i].w -= k; ed[i^1].w += k; res -= k; } } return flow - res; } inline void dinic(){ int flow = maxflow = 0; while( bfs() ){ while( flow=dfs( sp, inf ) ) maxflow += flow; } } int main(){ // freopen("in.txt", "r", stdin); while( ~scanf("%d%d", &n, &m) ){ init(); int cnt = 1; int num, t; for( int i=1; i<=n; i++ ){ scanf("%d%d%d%d", &s[i], &num, &e[i], &t); add( sp, i, num*t); sum += num*t; Time[cnt++] = s[i]; Time[cnt++] = e[i]; } sort( Time+1, Time+cnt+1 ); int top = unique(Time+1, Time+cnt+1)-(Time+1); tp = n+top+1; for( int i=1; i<=top; i++ ){ add( n+i, tp, m*(Time[i]-Time[i-1]) ); //时间区间编号i需要映射到i+n，避免与顾客的编号重复 for( int j=1; j<=n; j++ ){ if( s[j]<=Time[i-1] && e[j]>=Time[i] ) add( j, n+i, inf ); } } dinic(); if( maxflow==sum ) puts("Yes"); else puts("No"); } return 0; }