`

HDU 3572 Task Schedule (SAP)

    博客分类:
  • ACM
 
阅读更多

Task Schedule

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1911    Accepted Submission(s): 687


Problem Description
Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted and processed on different machines on different days. 
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.
 

 

Input
On the first line comes an integer T(T<=20), indicating the number of test cases.

You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.
 

 

Output
For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.

Print a blank line after each test case.
 

 

Sample Input
2 4 3 1 3 5 1 1 4 2 3 7 3 5 9 2 2 2 1 3 1 2 2
 

 

Sample Output
Case 1: Yes Case 2: Yes
 

 

Author
allenlowesy
 

 

Source
 

 

Recommend
zhouzeyong
 
 
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

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 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 t,cases=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        cnt=0;
        memset(head,-1,sizeof(head));
        src=0;
        int sum=0,MAX=0,p,s,e;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&p,&s,&e);
            sum+=p;
            MAX=max(MAX,e);
            addedge(src,i,p);   //源点与每个任务之间连一条边,容量为完成该任务所需处理次数
            for(int j=s;j<=e;j++)   //若第i个任务可以在Si至Ei天处理,则由该任务向这些天分别连一条边,容量为1,表示此任务每天只能被处理一次
                addedge(i,n+j,1);
        }
        des=n+MAX+1;
        for(int i=1;i<=MAX;i++)
            addedge(n+i,des,m); //从每一天连一条到汇点的边,容量为机器数M,表示每天可以处理M个任务
        n=des+1;
        if(SAP()==sum)  //若求出的最大流等于所有任务需要处理的次数之和,说明能完成任务
            printf("Case %d: Yes\n\n",++cases);
        else
            printf("Case %d: No\n\n",++cases);
    }
    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

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

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

    杭电ACMhdu1163

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

    hdu 5007 Post Robot

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

    Hdu1000—2169部分代码

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

    HDU acm-PPT课件

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

    hdu acm1166线段树

    hdu 1166线段树代码

    HDU最全ac代码

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

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

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

Global site tag (gtag.js) - Google Analytics