题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2883
Now N customers is coming. Customer i will arrive at time si
(which means the roaster cannot serve customer i until time si). He/She will
order ni kebabs, each one of which requires a total amount of ti unit time to
get it well-roasted, and want to get them before time ei(Just at exactly time ei
is also OK). The roaster has a big grill which can hold an unlimited amount of
kebabs (Unbelievable huh? Trust me, it’s real!). But he has so little charcoal
that at most M kebabs can be roasted at the same time. He is skillful enough to
take no time changing the kebabs being roasted. Can you help him determine if he
can meet all the customers’ demand?
Oh, I forgot to say that the roaster
needs not to roast a single kebab in a successive period of time. That means he
can divide the whole ti unit time into k (1<=k<=ti) parts such that any
two adjacent parts don’t have to be successive in time. He can also divide a
single kebab into k (1<=k<=ti) parts and roast them simultaneously. The
time needed to roast one part of the kebab well is linear to the amount of meat
it contains. So if a kebab needs 10 unit time to roast well, he can divide it
into 10 parts and roast them simultaneously just one unit time. Remember,
however, a single unit time is indivisible and the kebab can only be divided
into such parts that each needs an integral unit time to roast well.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define inf 0x7fffffff
using namespace std;
const int maxn=+;
const int M = ; int n,m,from,to;
int d[maxn];
struct node
{
int v,flow;
int next;
}edge[M*];
int head[maxn],edgenum; void add(int u,int v,int flow)
{
edge[edgenum].v=v ;edge[edgenum].flow=flow ;
edge[edgenum].next=head[u];
head[u]=edgenum++; edge[edgenum].v=u ;edge[edgenum].flow=;
edge[edgenum].next=head[v];
head[v]=edgenum++;
} int bfs()
{
memset(d,,sizeof(d));
d[from]=;
queue<int> Q;
Q.push(from);
while (!Q.empty())
{
int u=Q.front() ;Q.pop() ;
for (int i=head[u] ;i!=- ;i=edge[i].next)
{
int v=edge[i].v;
if (!d[v] && edge[i].flow>)
{
d[v]=d[u]+;
Q.push(v);
if (v==to) return ;
}
}
}
return ;
} int dfs(int u,int flow)
{
if (u==to || flow==) return flow;
int cap=flow;
for (int i=head[u] ;i!=- ;i=edge[i].next)
{
int v=edge[i].v;
if (d[v]==d[u]+ && edge[i].flow>)
{
int x=dfs(v,min(cap,edge[i].flow));
edge[i].flow -= x;
edge[i^].flow += x;
cap -= x;
if (cap==) return flow;
}
}
return flow-cap;
} int dinic()
{
int sum=;
while (bfs()) sum += dfs(from,inf);
return sum;
} int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-,sizeof(head));
edgenum=;
int s[],q[],e[],t[];
int time[maxn],cnt=;
memset(time,,sizeof(time));
int sum=;
for (int i= ;i<=n ;i++)
{
scanf("%d%d%d%d",&s[i],&q[i],&e[i],&t[i]);
sum += q[i]*t[i];
time[cnt++]=s[i];
time[cnt++]=e[i];
}
sort(time+,time+cnt);
int c=;
for (int i= ;i<cnt ;i++)
{
if (time[c] != time[i])
time[++c]=time[i];
}
from=n+c+;
to=from+;
for (int i= ;i<=n ;i++)
add(from,i,q[i]*t[i]);
for (int i= ;i<=c ;i++)
{
add(n+i,to,m*(time[i]-time[i-]));
for (int j= ;j<=n ;j++)
{
if (s[j]<=time[i-] && time[i]<=e[j])
add(j,n+i,inf);
}
}
if (sum==dinic()) printf("Yes\n");
else printf("No\n");
}
return ;
}