建图 源点 -> 每个人 -> 每段时间 -> 汇点
时间要离散化一下 分成一些时间段
权 inf ti[i]*(time[i]-time[i-1]) m*(time[i]-time[i-1])
n人 m个机器
开始时间 总共要的数目 底线时间 每个所需时间
如果可以达到输出Y 否则N
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<math.h> using namespace std;
#define inf 100000000
#define MAXN 300
#define MAXN1 200000
int si[MAXN+],ni[MAXN+],ei[MAXN+],ti[MAXN+];
int time[MAXN*+],S,T;
int head[*MAXN];
int cnt; struct edg
{
int w,next,to; }x[MAXN1+]; void add(int u,int v,int w)
{
x[cnt].next=head[u];
x[cnt].to=v;
x[cnt].w=w;
head[u]=cnt++;
}
int vis[*MAXN]; int bfs()
{
memset(vis,-,sizeof(vis));
vis[S]=;
queue<int>q1;
q1.push(S); while(!q1.empty())
{
int now=q1.front();
q1.pop();
for(int j=head[now];j!=-;j=x[j].next)
{
if(vis[x[j].to]<&&x[j].w)
{
vis[x[j].to]=vis[now]+;
q1.push(x[j].to);
}
}
}
return vis[T]!=-;
}
int dfs(int u,int w)
{
int ans=; if(u==T)
return w;
int i; for(i=head[u];i!=-;i=x[i].next)
{
if(vis[x[i].to]==vis[u]+&&x[i].w)
{
int b=dfs(x[i].to,min(w-ans,x[i].w));
x[i].w-=b;
x[i^].w+=b;
ans=ans+b;
}
}
return ans;
}
int main()
{
int n,m; while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j;
int c1,sum=;
cnt=; for(i=;i<=n;i++)
{
scanf("%d%d%d%d",&si[i],&ni[i],&ei[i],&ti[i]);
time[cnt++]=si[i];
time[cnt++]=ei[i];
sum=sum+ni[i]*ti[i];
}
sort(time,time+cnt);
c1=;
for(i=;i<cnt;i++)
{
if(time[i]!=time[i-])
time[c1++]=time[i];
}
S=;
T=n+c1+;
cnt=; memset(head,-,sizeof(head));
for(i=;i<=n;i++)
add(S,i,ni[i]*ti[i]),add(i,S,); for(i=;i<c1;i++)
{
if(i==) //0的时候没有i-1
{
add(n+i+,T,m*time[i]);
add(T,n+i+,);
}
else
{
add(n+i+,T,m*(time[i]-time[i-]));
add(T,n+i+,);
} for(j=;j<=n;j++)
{
int a; if(i==)
a=;
else
a=time[i-];
if(si[j]<=a&&time[i]<=ei[j])
{
add(j,n+i+,inf);
add(n+i+,j,);
}
}
}
int ans=;
while(bfs())
ans=ans+dfs(S,inf); if(ans>=sum)
printf("Yes\n");
else
printf("No\n");
} return ;
}