hdoj 2883 kebab 【时间区间离散化 + 最大流】

kebab

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1273    Accepted Submission(s): 532

Problem Description

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.

Input

There are multiple test cases. The first line of each case contains two positive integers N and M. N is the number of customers and M is the maximum kebabs the grill can roast at the same time. Then follow N lines each describing one customer, containing four
integers: si (arrival time), ni (demand for kebabs), ei (deadline) and ti (time needed for roasting one kebab well).

There is a blank line after each input block.

Restriction:

1 <= N <= 200, 1 <= M <= 1,000

1 <= ni, ti <= 50

1 <= si < ei <= 1,000,000

Output

If the roaster can satisfy all the customers, output “Yes” (without quotes). Otherwise, output “No”.

Sample Input

2 10
1 10 6 3
2 10 4 2

2 10
1 10 5 3
2 10 4 2

Sample Output

Yes
No

建议先做 hdoj 3572

看到这道题,知道要离散化,也知道怎么将时间区间离散化,但不知道怎么处理建边。o(╯□╰)o  不得不ORZ神牛了

题意:有 N 个人来吃烤肉,每个人到达时间为 si,离开时间为 ei,点的烤肉数量为 ni,烤好一份肉所需时间为 ti。现在只有一台烧烤机,该机器每个单位时间能烤 M 份肉。问能否满足所有顾客的需求。

思路:先用数组rec记录所有si和ei,排序去重(离散化),保证区间不重叠。

把相邻时间区间虚拟成点,即把区间 [ rec[i], rec[i+1] ]当做一个点。

将每个人对时间点的建边处理变成对时间区间的建边处理。建好图,跑一次最大流判断是否满流即可。

建图:设置超级源点source,超级汇点sink

1,source到每个人i建边,容量为ni * ti;

2,相邻时间区间[ rec[i], rec[i+1] ] 到sink建边,容量为(rec[i+1] - rec[i]) * M,表示同时可以烤M个;

3,判断每个人的时间区间[si, ei]是否包含离散化后的相邻时间区间[ rec[i], rec[i+1] ]。若包含表示在该区间内可以提供足够的时间供给这个人烤肉,则建边容量无穷大,否则不建边。

AC代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 800
#define MAXM 200000+10
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
    int from, to, cap, flow, next;
};
Edge edge[MAXM];
int head[MAXN], edgenum, cur[MAXN];
int dist[MAXN];
bool vis[MAXN];
int N, M;
void init()
{
    edgenum = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
    Edge E1 = {u, v, w, 0, head[u]};
    edge[edgenum] = E1;
    head[u] = edgenum++;
    Edge E2 = {v, u, 0, 0, head[v]};
    edge[edgenum] = E2;
    head[v] = edgenum++;
}
int sumflow;//记录源点传入的总流量
int source, sink;//超级源点 超级汇点
struct Node
{
    int s, n, e, t;
};
Node num[210];
int rec[500];
void getMap()
{
    source = 0;
    int len = 1;
    sumflow = 0;
    for(int i = 1; i <= N; i++)
    {
        scanf("%d%d%d%d", &num[i].s, &num[i].n, &num[i].e, &num[i].t);
        addEdge(source, i, num[i].n * num[i].t);
        sumflow += num[i].n * num[i].t;
        rec[len++] = num[i].s;
        rec[len++] = num[i].e;
    }
    sort(rec+1, rec+len);
    //去重
    int R = 2;
    for(int i = 2; i < len; i++)//滚动数组优化
        if(rec[i] != rec[i-1])
            rec[R++] = rec[i];//得到R-1个端点
    sort(rec+1, rec+R);
    //R-1个端点 R-2个区间
    sink = N+R-1;//超级汇点
    for(int i = 1; i < R-1; i++)//对R-2个区间处理
        addEdge(i+N, sink, (rec[i+1]-rec[i]) * M);
    for(int i = 1; i <= N; i++)//对每个人的用餐时间区间 处理
    {
        for(int j = 1; j < R-1; j++)//枚举R-2个区间
        {
            if(num[i].s <= rec[j] && num[i].e >= rec[j+1])//时间容纳区间 容量无穷大
                addEdge(i, j+N, INF);
        }
    }
}
bool BFS(int s, int t)
{
    queue<int> Q;
    memset(dist, -1, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    vis[s] = true;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            Edge E = edge[i];
            if(!vis[E.to] && E.cap > E.flow)
            {
                dist[E.to] = dist[u] + 1;
                if(E.to == t) return true;
                vis[E.to] = true;
                Q.push(E.to);
            }
        }
    }
    return false;
}
int DFS(int x, int a, int t)
{
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int &i = cur[x]; i != -1; i = edge[i].next)
    {
        Edge &E = edge[i];
        if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), t)) > 0)
        {
            edge[i].flow += f;
            edge[i^1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}
int Maxflow(int s, int t)
{
    int flow = 0;
    while(BFS(s, t))
    {
        memcpy(cur, head, sizeof(head));
        flow += DFS(s, INF, t);
    }
    return flow;
}
int main()
{
    while(scanf("%d%d", &N, &M) != EOF)
    {
        init();
        getMap();
        if(Maxflow(source, sink) == sumflow)//满流
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

kebab

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1273    Accepted Submission(s): 532

Problem Description

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.

Input

There are multiple test cases. The first line of each case contains two positive integers N and M. N is the number of customers and M is the maximum kebabs the grill can roast
at the same time. Then follow N lines each describing one customer, containing four integers: si (arrival time), ni (demand for kebabs), ei (deadline) and ti (time needed for roasting one kebab well).

There is a blank line after each input block.

Restriction:

1 <= N <= 200, 1 <= M <= 1,000

1 <= ni, ti <= 50

1 <= si < ei <= 1,000,000

Output

If the roaster can satisfy all the customers, output “Yes” (without quotes). Otherwise, output “No”.

Sample Input

2 10
1 10 6 3
2 10 4 2

2 10
1 10 5 3
2 10 4 2

Sample Output

Yes
No

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-29

hdoj 2883 kebab 【时间区间离散化 + 最大流】的相关文章

hdoj 2883 kebab 【经典最大流】

题目:hdoj 2883 kebab 题意:现在有n个人要烤肉,有m个烤肉架,然后给出每个人的烤肉开始时间si,结束时间ei,以及要烤肉的串数num,还有拷一串的时间ti,然后问你能不能满足所有人的要求. 分析:这是一个比较经典的最大流,经典在于建图方法,这个题目难点在于时间跨度在0---100 0000,如果时间短的话就可以用题目3572的做法了.点击打开链接 后面看了别人的建图方法,确实比较经典,经典在于把区间缩点了,这个题目的难点在于时间跨度大,那么我们可以把所有的时间点记录下来,然后排序

hdu 2883 kebab(时间区间压缩 &amp;amp;&amp;amp; dinic)

kebab Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1243    Accepted Submission(s): 516 Problem Description Almost everyone likes kebabs nowadays (Here a kebab means pieces of meat grilled on

hdu 2883 kebab(时间区间压缩 &amp;&amp; dinic)

kebab Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1243    Accepted Submission(s): 516 Problem Description Almost everyone likes kebabs nowadays (Here a kebab means pieces of meat grilled on

HDU 2883 kebab(最大流)

HDU 2883 kebab 题目链接 题意:有一个烧烤机,每次最多能烤 m 块肉,现在有 n 个人来买烤肉,每个人到达时间为 si,离开时间为 ei,点的烤肉数量为 ci,每个烤肉所需烘烤时间为 di,注意一个烤肉可以切成几份来烤 思路:把区间每个点存起来排序后,得到最多2 * n - 1个区间,这些就表示几个互相不干扰的时间,每个时间内只可能有一个任务器做,这样建模就简单了,源点连向汇点,容量为任务需要总时间,区间连向汇点,容量为区间长度,然后每个任务如果包含了某个区间,之间就连边容量无限大

HDU 3572 【最大流 &amp;&amp; 时间区间建图】

Task Schedule Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5398    Accepted Submission(s): 1742 Problem Description Our geometry princess XMM has stoped her study in computational geometry t

HDU - 2883 kebab (最大流)

题目大意:有一个烤肉老板,每个单位时间可以完成M的烤肉 现在有N位客人,给出每位客人来的时间,走的时间,烤肉的数量和每串烤肉所需的单位时间 问这个老板能否完成每位客人的需求 解题思路:这题和HDU 3572相似,但又不能像那题那样做,因为这题时间长度有点大 所以将时间区间当成一个点,将该区间连向超级汇点,容量为区间长度*M 将所有客人连向超级源点,容量为烤肉数量*每串烤肉所需时间 接下来的难点就是怎么将客人和时间区间连起来了 如果时间区间在客人来的时间和走的时间这段区间内,就表明这段时间可以用来

hdu 2883 kebab 网络流

题目链接: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 delicio

Sql server 查询指定时间区间工作日数、休息日数等日期操作

1.查询指定时间区间的工作日 这个主要难点是法定节假日,国家的法定节假日每年都不一样,还涉及到调休,所以我们设计一个假日表.主要字段有年份,类型(是否调休),假期日期.如下: CREATE TABLE [dbo].[Holidays]( [ID] [int] IDENTITY(1,1) NOT NULL, [Holiday] [datetime2](7) NULL,--假期日期 [YearS] [char](4) NULL,--年份 [daytype] [int] NULL--类型 ) 添加好当

获取指定时间区间作业运行情况

背景:数据库服务器定期重启,想知道重启期间对作业的影响.通俗点就是服务器在重启这段时间,有哪些作业计划要运行,重启后是否要手动执行这些作业?第一次重启的时候,按照最笨的方式,把所有作业看一遍,然后人为判断有哪些作业将受到影响,再根据作业具体代码,确定是否需手动执行.后来老大说要弄个过程出来,通过传入起止时间参数,返回区间内的作业计划.PS:参考各类资料,修改过很多遍,最后成型在6月初,很多细节上的修改自己也记不清楚了,一直懒得整理.先放上代码,以及效果图. 1 /****************