题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2883

Almost everyone likes kebabs nowadays (Here a kebab means pieces of meat grilled on a long thin stick). Have you, however, considered about the hardship of a kebab roaster while enjoying the delicious food? Well, here's a chance for you to help the poor roaster make sure whether he can deal with the following orders without dissatisfying the customers.

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.

题意描述:有n个人来烤肉店吃烤肉,每个人在si 时刻来ei 时刻离开并且点了ni 份,每份烤肉要烤到ti 个单位时间才算烤熟,烤肉店里可以同时烤m份。问是否有一种计划使得n个人都可以拿到自己的ni 份。
算法分析:这道题本身不是很难,网络流的模型也很常见,但是这道题中(si,ei)的时间跨度很大(1<=si<=ei<=1000000),所以不能把时间区间直接拆分开建立模型,这样顶点个数太多,会超时。这里,介绍一下学到的新技巧,我们可以把时间区间压缩:time[]里保存全部的si 和 ei ,这样time[i]-time[i-1]就表示一段时间区间了,如果这段时间区间在[si,ei]中,那么就把第 i 个人这个顶点和第 i 个时间区间相连接,然后,from->第 i 个人,第 i 个时间区间->to。这样,每一条s-t路径就表示一种烤肉的时间计划了。 
 #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 ;
}

最新文章

  1. php字符截取
  2. spark统计
  3. linux web服务器必需的库文件
  4. 第五章 CSS页面布局基础
  5. 太受不了了,,REST_FRAMEWORK太方便啦~~
  6. 27个Jupyter Notebook使用技巧及快捷键(翻译版)
  7. Spring搭建MVC WEB项目[转]
  8. Oracle数据泵(上)
  9. delphi引用别的单元时问题
  10. C# MessageBox.Show每隔3秒自动关闭
  11. javascript面向对象习题答案
  12. Python3字典
  13. LG4213 【【模板】杜教筛(Sum)】
  14. spring定时任务配置,以及不执行的解决办法
  15. Linux 线程调度与优先级
  16. 微信小游戏5.2.2 没有xml支持库的问题解决
  17. iOS 功能代码 上传到 远程 码云私有库
  18. perl发送post数据
  19. 理解面向对象编程---C#控制台实现52张扑克牌的分法
  20. OSX 10.11.1 预览照片绿屏的问题

热门文章

  1. js构造函数,索引数组和属性的属性
  2. 转:浅谈关于b、h标签的优化技巧
  3. 重回程序员之路。重写博客。我的ecshop小京东二开问题汇总与解决方案。
  4. PopupWindow的简单使用
  5. Python初学者笔记:打印出斐波那契数列的前10项
  6. tomcat datasource
  7. UIViewAnimationOptions swift 2
  8. DISP_FUNCTION用法
  9. 创建自己的oracle解释计划
  10. Socket(1)