很好的题目。
有不多于200个任务，每个任务要在si到ei这个时间段内完成，每个任务的任务量是ti*ni，只有一台机器，且其单位时间内可完成的任务量为m。
现在问你，能否使所有的任务全部在规定的时间段内完成。
首先把所有的时间都提取出来，排序，得到2*n-1个时间区间。
网络流建模。首先创建一个超级源点和超级汇点。源点连接n个任务，与每个任务的边的容量为ni*ti，汇点连接2*n-1个时间区间，容量为时间长度与m的乘积。同时在任务和时间区间之间也需要连边，如果某个任务的时间和时间区间有公共时间段，那么他们之间连一条边，边容量为公共时间长度乘以m。这样我们只需要求整个网络的最大流，看看是否与总的工作量相等即可。
很有意思。嘿嘿
召唤代码君：
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 777
#define Inf ~0U>>1
using namespace std;
int c[maxn][maxn],d[maxn],can[maxn];
int n,m,s,t,tot,ans;
int ni[maxn],ti[maxn],si[maxn],ei[maxn];
int T[maxn],N;
vector<int> v[maxn];
void _init()
{
s=1,t=1+3*n,N=0,ans=tot=0;
for (int i=1; i<=1+3*n; i++)
{
v[i].clear();
for (int j=1; j<=1+3*n; j++) c[i][j]=0;
}
}
void graph_build()
{
int L,R;
sort(T+1,T+1+2*n);
for (int i=1; i<=n; i++)
{
c[1][i+1]=ni[i]*ti[i];
v[1].push_back(i+1),v[i+1].push_back(1);
}
for (int i=1; i<2*n; i++)
{
c[n+1+i][3*n+1]=(T[i+1]-T[i])*m;
v[n+1+i].push_back(3*n+1),v[3*n+1].push_back(n+1+i);
}
for (int i=1; i<=n; i++)
for (int j=1; j<2*n; j++)
{
L=max(si[i],T[j]);
R=min(ei[i],T[j+1]);
if (L>=R) continue;
c[1+i][n+1+j]=(R-L)*m;
v[1+i].push_back(n+1+j),v[n+1+j].push_back(1+i);
}
}
void bfs()
{
for (int i=s; i<=t; i++) d[i]=999999,can[i]=0;
queue<int> Q;
Q.push(t);
d[t]=0;
while (!Q.empty())
{
int cur=Q.front();
Q.pop();
for (unsigned i=0; i<v[cur].size(); i++)
{
if (c[v[cur][i]][cur]<=0) continue;
if (d[cur]+1<d[v[cur][i]])
{
d[v[cur][i]]=d[cur]+1;
Q.push(v[cur][i]);
}
}
}
}
int dfs(int cur,int num)
{
if (cur==t) return num;
int k,tmp=num;
for (unsigned i=0; i<v[cur].size(); i++)
{
if (c[cur][v[cur][i]]<=0 || d[v[cur][i]]+1!=d[cur] || can[v[cur][i]]) continue;
k=dfs(v[cur][i],min(num,c[cur][v[cur][i]]));
if (k) c[cur][v[cur][i]]-=k,c[v[cur][i]][cur]+=k,num-=k;
}
if (num) can[cur]=1;
return tmp-num;
}
int Dinic()
{
for (bfs(); d[s]<3*n+1; bfs()) ans+=dfs(1,Inf);
return ans;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
_init();
for (int i=1; i<=n; i++)
{
scanf("%d%d%d%d",&si[i],&ni[i],&ei[i],&ti[i]);
tot+=ni[i]*ti[i];
T[++N]=si[i],T[++N]=ei[i];
}
graph_build();
if (Dinic()==tot) puts("Yes");
else puts("No");
}
return 0;
}