• 【tyvj1517】飘飘乎居士的乌龟

    【tyvj1517】飘飘乎居士的乌龟

    背景Background飘飘乎居士养了乌龟。当然,这些乌龟是用来出售赚取利润的。描述Description飘飘乎居士的乌龟被安置在了m个窝中。现在,飘飘乎居士已经接到了n个人的定购通知,他们会按顺序在来挑选乌龟,其中,第i个人会在pi个窝中挑选乌龟,但最多只想买xi只乌龟。另外,在第i个人购买完乌龟以后,飘飘乎居士会将指定的qi个窝中的龟进行调整,他可以任意调换指定的qi个窝中乌龟数量。飘飘乎希望知道,在n个人购买完乌龟后,他最...

    02014年5月4日1,089最大流
  • 网络流&费用流模板

    网络流&费用流模板

    网络流dinic[crayon-5a5ea4378fb5d678316048/]最小费用最大流spfa[crayon-5a5ea4378fb69184261668/]zkw费用流[crayon-5a5ea4378fb70054493743/] 

    142014年5月1日7,073最小割,费用流,最大流
  • 【bzoj1433】[ZJOI2009]假期的宿舍

    【bzoj1433】[ZJOI2009]假期的宿舍

    DescriptionInputOutputSampleInput13110010011100100SampleOutputˆˆHINT对于30%的数据满足1≤n≤12。对于100%的数据满足1≤n≤50,1≤T≤20。题解源点向所有有床位的连边需要床位的向汇点连边如果i可以睡j的床i向j‘连边[crayon-5a5ea43790dbc890286745/] ...

    02014年3月27日2,537最大流
  • 【tyvj1431】分配任务

    【tyvj1431】分配任务

    描述Description随着tyvj发展越来越大,管理员的任务越来越重,如何合理的分配任务,成为了一个可研究的命题。Tyvj当前一共有M个需要做的任务,和N位管理员。每一个管理员的上线时间并不是固定的,每一个人有d[i]单位的上线时间,每一位管理员一个单位的时间可以完成一个任务,且一个任务只能由一个管理员来完成(如果更多的管理员参与进来,可能会造成混乱)。每一位管理员的能力有所不同,所以能完成的任务集合可能不相同。最...

    02014年3月26日1,173最大流
  • 【th04】河城荷取

    【th04】河城荷取

    Description在幻想乡,河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外,还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大,所以为它充能是一件很麻烦的事。人形一共有N个电能池,编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口,而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道,每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个...

    02014年3月23日1,347最大流
  • 【bzoj1305】[CQOI2009]dance跳舞

    【bzoj1305】[CQOI2009]dance跳舞

    Description一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?Input第一行包含两个整数n和k。以下n行每行包含n个字符,其...

    02014年3月13日3,592最大流,二分法
  • 【网络流24题】圆桌聚餐

    【网络流24题】圆桌聚餐

    «问题描述: 假设有来自m个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri(i=1,2,3...m),。会议餐厅共有n张餐桌,每张餐桌可容纳ci(i=1,2...n)个代表就餐。 为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法, 给出满足要求的代表就餐方案。 «编程任务: 对于给定的代表数和餐桌数以及餐桌容量,编程计算满足要求的代表就餐方案。 «数据输入...

    32014年3月8日2,761最大流
  • 【网络流24题】魔术球问题

    【网络流24题】魔术球问题

    Description假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,4的球。(1)每次只能在某根柱子的最上面放球。(2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。试设计一个算法,计算出在n根柱子上最多能放多少个球。例如,在4根柱子上最多可放11个球。编程任务:对于给定的n,计算在n根柱子上最多能放多少个球。InputFormat文件第1行有1个正整数n,表示柱子数。OutputFormat程序运行结束时,将n...

    42014年3月7日3,912最大流
  • 【bzoj1189】[HNOI2007]紧急疏散evacuate

    【bzoj1189】[HNOI2007]紧急疏散evacuate

     Description发生了火警,所有人员需要紧急疏散!假设每个房间是一个NM的矩形区域。每个格子如果是'.',那么表示这是一块空地;如果是'X',那么表示这是一面墙,如果是'D',那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没...

    62014年3月7日3,643二分法,最大流,广度搜索
  • 【codevs1034】家园

    【codevs1034】家园

    题目描述 Description由于人类对自然的疯狂破坏,人们意识到在大约2300年之后,地球不能再居住了,于是在月球上建立了新的绿地,以便在需要时移民。令人意想不到的是,2177年冬由于未知的原因,地球环境发生了连锁崩溃,人类必须在最短的时间内迁往月球。现有n个太空站处于地球与月球之间(编号1..n),m艘公共交通太空船在其中来回穿梭,每个太空站Si可容纳无限的人,每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi,将周期性...

    02014年2月28日1,454最大流
  • 【bzoj1066】[SCOI2007]蜥蜴

    【bzoj1066】[SCOI2007]蜥蜴

    Description在一个r行c列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。每行每列中相邻石柱的距离为1,蜥蜴的跳跃距离是d,即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减1(如果仍然落在地图内部,则到达的石柱高度不变),如果该石柱原来高度为1,则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同...

    02014年2月22日3,677最大流
  • 【bzoj1834】[ZJOI2010]network 网络扩容

    【bzoj1834】[ZJOI2010]network 网络扩容

    Description给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求:1、在不扩容的情况下,1到N的最大流;2、将1到N的最大流增加K所需的最小扩容费用。Input输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。Output输出文件一行包含两个整数,分别表示...

    02014年2月21日3,872费用流,最大流