费用流 - hzwer.com

「百度之星2017」程序设计大赛初赛(B)
好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-67737396e4ee7851786612/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\)，和小等于m的对于元素个数很多的集合，每个集合bfs一次，预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少，建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力，结果还过了[crayon-67737396e4ef3009052636/]1005.度度熊的交易计划预...
22017年8月13日9,640递推与动规,贪心,费用流,floyd,广度搜索

2017ACM萧山训练第1场(NEERC 2016)
队友做的题目我并不是非常懂。。。A.[Neerc2016]Abbreviation字符串模拟E.[Neerc2016]ExpecttoWait如果对于等待的人数维护一个关于时间的前缀和那么我们就得到了一个很长的前缀和序列，我们注意到初始车辆为x，实际上就是询问这个序列大于x的前缀和的和那么对于时间离散化以后，就是询问大于x的段的加权和对所有的段从小到大排序，依次处理[crayon-67737396e644b161238631/]G.[Neerc2016]GameonGraph第二个人先手的状态...
02017年8月7日6,124模拟,递推与动规,费用流,树形动规,博弈论
「FJ2015集训」贪吃蛇
最近lwher迷上了贪吃蛇游戏，在玩了几天却从未占满全地图的情况下，他不得不承认自己是一个弱菜，只能改去开发一款更弱的贪吃蛇游戏。在开发的过程中，lwher脑洞大开，搞了一个多条蛇的模式。但由于这种模式太难操作，于是他只好改变游戏的玩法，稍微变化一下游戏目标。新的游戏是这样的：一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接)，且只是占据两个格子...
62015年7月13日7,413费用流,有上下界网络流,随机化
「BZOJ3308」九月的咖啡店
Description深绘里在九份开了一家咖啡让，如何调配咖啡民了她每天的头等大事我们假设她有N种原料，第i种原料编号为i,调配一杯咖啡则需要在这里若干种兑在一起。不过有些原料不能同时在一杯中，如果两个编号为i,j的原料，当且仅当i与j互质时，才能兑在同一杯中。现在想知道，如果用这N种原料来调同一杯咖啡，使用的原料编号之和最大可为多少。Input一个数字NOutput如题SampleInput10SampleOutput30HINT1<=N<=2...
62015年6月2日6,005费用流
「BZOJ3638 / 3272」Cf172 k – Maximum Subsequence Sum
Description给一列数，要求支持操作：1.修改某个数的值2.读入l,r,k，询问在[l,r]内选不相交的不超过k个子段，最大的和是多少。InputThefirstlinecontainsintegern(1 ≤ n ≤ 105),showinghowmanynumbersthesequencehas.Thenextlinecontainsnintegersa1, a2, ..., an(|ai| ≤ 500).Thethirdlinecontainsintegerm(1 ≤ m ≤ 105)—thenumberofqueries.Thenextmlinescontainthequeriesintheformat,giveninthestate...
22015年4月16日5,045费用流,线段树
「BZOJ1283」序列
Description给出一个长度为的正整数序列Ci，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过K(K,M<=100)个，并且选出的元素之和最大。Input第1行三个数N,m,k。接下来N行，每行一个字符串表示Ci。Output最大和。SampleInput10534446666644SampleOutput30HINT20%的数据:n<=10。100%的数据：N<=1000，k,m<=100。Ci<=20000。题解线性规划裸题复习模板ing题解请看：http://hzwer.c...
02015年3月25日4,918费用流
「BZOJ1927」[SDOI2010] 星际竞速
题目描述Description10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座α星的悠悠也是其中之一。赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发，访问这N颗行星每颗恰好一次，首先完成这一目标的人获得胜利。由于赛制非常开放，很多人驾驶着千奇百怪的自制...
72015年2月5日6,145费用流
「BZOJ3876」[Ahoi2014] 支线剧情
Description「故事背景」宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。「问题描述」JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前往Ki种不同的新的剧情点。当然如果为0...
92015年1月25日6,936费用流,有上下界网络流
「网络流练习」defuze
连锁炸弹是恐怖分子最近开始使用的一种威力巨大的爆炸物。其复杂的结构使拆除它的难度大大增加了。一个连锁炸弹由m个引爆装置和n枚炸弹组成。每个引爆装置中有n条信号线分别与这n枚炸弹相连（1号线连接炸弹1，2号线连接炸弹2，……）。与一枚炸弹相连的m条信号线中只有一条是“安全线”——剪断后可以拆除炸弹，而剪断其它信号线则引爆炸弹。专业的技术人员将给出一个m×n的表格。其中第i行第j列显示了引爆装置i与炸弹j连接的信号线...
02015年1月4日4,558费用流
「网络流24题」最长k可重区间集问题
搬运byvoid的题解「问题分析」最大权不相交路径问题，可以用最大费用最大流解决。「建模方法」方法1按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S'。1、连接S到S'一条容量为K，费用为0的有向边。2、从S'到每个<i.a>连接一条容量为1，费用为0的有向边。3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。4、从每个顶点<i.a>到<i.b>连...
22014年12月27日5,873费用流
「BZOJ1449 / 2895」[JSOI2009] 球队收益
Description在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球员的奖金就多嘛)其中x,y分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了a[i]场胜利和b[i]场失利。而接下来还有m场比赛要进行。问联盟球队的最小总支出是多少。Input第一行n，m接下来n行每行4个整数a[i],b[i],Ci,Di再接下来m行每行...
22014年12月21日4,706费用流
「BZOJ2893」征服王
Description虽然春希将信息传递给了雪菜，但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能，对雪菜的脑内芯片进行了直连-hack。进入到雪菜内部的春希发现（这什么玩意。。），雪菜的脑部结构被分成了n个块落，并且一些块落之间被有向边连接着。由于四分五裂的脑部，雪菜关于春希的记忆也完全消失，春希为了恋人，启动了inversionprocess.在inversionprocess中，要想使雪菜回到正常状态，需要纳米机器人的帮助。...
02014年12月16日5,352费用流,图的连通