`

HDU 2833 kebab (SAP)

    博客分类:
  • ACM
阅读更多

kebab

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 494    Accepted Submission(s): 215


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
 

 

Source
 

 

Recommend
gaojie
 

 

将所有的到达时间和结束时间按升序排序,得到 x <= 2n-1 个时间区间。建立网络流模型:s为源,t为汇,每个顾客i作为一个结点并连边(s, i, ni*ti),每个区间j作为一个结点并连边(j, t, (ej-sj)*M),其中sj, ej分别表示区间j的起始时间和终止时间。对任意顾客i和区间j,若 [sj, ej] 完全包含在 [si, ei] 之中,则连边(i, j, INF)。若最大流等于 ∑ni*ti 则是 Yes,否则是 No。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int VM=1010;
const int EM=500010;
const int INF=0x3f3f3f3f;

int n,m,cnt,head[VM];
int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM];
    //dep表示每个点的距离标记,gap表示距离为i的点有多少个,cur用于当前孤优化,
    //aug记录找到的增广路流量,path记录找到的增广路的路径。

struct Edge{
    int u,v,nxt;
    int cap;
}edge[EM];

void addedge(int cu,int cv,int cw){
    edge[cnt].u=cu;  edge[cnt].v=cv;  edge[cnt].cap=cw;
    edge[cnt].nxt=head[cu];  head[cu]=cnt++;
    edge[cnt].u=cv;  edge[cnt].v=cu;  edge[cnt].cap=0;
    edge[cnt].nxt=head[cv];  head[cv]=cnt++;
}

int src,des;

int SAP(int n){
    int max_flow=0,u=src,v;
    int id,mindep;
    aug[src]=INF;
    pre[src]=-1;
    memset(dep,0,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=n;
    for(int i=0;i<=n;i++)
        cur[i]=head[i]; // 初始化当前弧为第一条弧
    while(dep[src]<n){
        int flag=0;
        if(u==des){
            max_flow+=aug[des];
            for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
                id=cur[v];
                edge[id].cap-=aug[des];
                edge[id^1].cap+=aug[des];
                aug[v]-=aug[des];   // 修改可增广量,以后会用到
                if(edge[id].cap==0) // 不回退到源点,仅回退到容量为0的弧的弧尾
                    u=v;
            }
        }
        for(int i=cur[u];i!=-1;i=edge[i].nxt){
            v=edge[i].v;    // 从当前弧开始查找允许弧
            if(edge[i].cap>0 && dep[u]==dep[v]+1){  // 找到允许弧
                flag=1;
                pre[v]=u;
                cur[u]=i;
                aug[v]=min(aug[u],edge[i].cap);
                u=v;
                break;
            }
        }
        if(!flag){
            if(--gap[dep[u]]==0)    /* gap优化,层次树出现断层则结束算法 */
                break;
            mindep=n;
            cur[u]=head[u];
            for(int i=head[u];i!=-1;i=edge[i].nxt){
                v=edge[i].v;
                if(edge[i].cap>0 && dep[v]<mindep){
                    mindep=dep[v];
                    cur[u]=i;   // 修改标号的同时修改当前弧
                }
            }
            dep[u]=mindep+1;
            gap[dep[u]]++;
            if(u!=src)  // 回溯继续寻找允许弧
                u=pre[u];
        }
    }
    return max_flow;
}

int main(){

    //freopen("input.txt","r",stdin);

    int s[210],e[210],t[210],a[1010],k[210];
    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        memset(head,-1,sizeof(head));
        int sum=0,tot=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&s[i],&k[i],&e[i],&t[i]);
            sum+=k[i]*t[i];
            addedge(0,i,k[i]*t[i]); //将源点和每个顾客相连,容量为ki*ti,
            a[tot++]=s[i];  //记录每一个到达时间和离开时间,删除重复的时间点
            a[tot++]=e[i];
        }
        sort(a,a+tot);
        tot=unique(a,a+tot)-a;
        src=0,des=n+tot;
        int nodenum=des+1;
        for(int i=0;i<tot-1;i++){
            addedge(n+1+i,des,(a[i+1]-a[i])*m); //相邻2个时间点为一个时间段,每一个时间段作为一个节点和汇点相连,容量为时间段的长度*m
            for(int j=1;j<=n;j++)
                if(s[j]<=a[i] && e[j]>=a[i+1])
                    addedge(j,n+1+i,INF);   //若一个时间段在顾客的到达和离开时间段内,则该顾客节点和时间段节点连接容量为INF的边
        }
        if(SAP(nodenum)==sum)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

 

 

分享到:
评论

相关推荐

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu2101解决方案

    hdu2101AC代码

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU最全ac代码

    HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...

    hdu acm1166线段树

    hdu 1166线段树代码

Global site tag (gtag.js) - Google Analytics