费用流 - Page 2

「vijos1891」学姐的逛街计划
描述doc最近太忙了,每天都有课.这不怕,doc可以请假不去上课.偏偏学校又有规定,任意连续n天中,不得请假超过k天.doc很忧伤,因为他还要陪学姐去逛街呢.后来,doc发现,如果自己哪一天智商更高一些,陪学姐逛街会得到更多的好感度.现在doc决定做一个实验来验证自己的猜想,他拜托小岛预测出了自己未来3n天中,每一天的智商.doc希望在之后的3n天中选出一些日子来陪学姐逛街,要求在不违反校规的情况下,陪学姐逛街的日子自己智商的总和最大.可是...
02014年10月25日4,750费用流

「BZOJ1520」[POI2006] Szk – Schools
DescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解这个裸的费用流吧。。正好复习下zkw[crayon-6740171e1986b176368032/] ...
12014年10月20日4,503费用流
「BZOJ2324」[ZJOI2011] 营救皮卡丘
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧...
02014年10月9日7,567费用流,floyd
「BZOJ1930」[SHOI2003] pacman吃豆豆
Description两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。Input第一行为一个整数N，表示豆豆的数目。接下来N行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。O...
112014年6月14日6,103费用流
「BZOJ2661」[BJ WC2012] 连连看
Description 凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。Input 只有一行...
82014年6月5日4,717费用流
「NOIP模拟赛」密码锁
题目描述hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有...
42014年6月1日5,270费用流,广度搜索,状压动规,记忆化搜索
NOI2008志愿者招募
Description申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N天才能完成，其中第i天至少需要Ai个人。布布通过了解得知，一共有M类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天，招募费用是每人Ci元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，...
22014年5月31日4,787费用流
「BZOJ3280」小R的烦恼
Description小R最近遇上了大麻烦，他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他，但是要求小R帮助他一起解决一个难题。问题是这样的，程设老师最近要进行一项邪恶的实验来证明P=NP，这个实验一共持续n天，第i天需要a[i]个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了m所大学，第j所大学共有l[j]个研究生，同时雇佣这所大学的一个研究生需要p[j]元...
02014年5月8日3,959费用流
「BZOJ2879」[Noi2012] 美食节
DescriptionCZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现，美食节...
42014年5月1日7,007费用流
「BZOJ1070」[SCOI2007] 修车
Description同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。Input第一行有两个m,n，表示技术人员数与顾客数。接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的...
122014年5月1日8,566费用流
网络流&费用流模板
网络流dinic[crayon-6740171e38325795414734/]最小费用最大流spfa[crayon-6740171e38330268279514/]zkw费用流[crayon-6740171e38337102202302/]
132014年5月1日18,215最小割,费用流,最大流
「BZOJ2245」[SDOI2011] 工作安排
Description你的公司接到了一批订单。订单要求你的公司提供n类产品，产品被编号为1~n，其中第i类产品共需要Ci件。公司共有m名员工，员工被编号为1~m员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造，不可以由某名员工制造一部分配件后，再转交给另外一名员工继续进行制造。我们用一个由0和1组成的m*n的矩阵A来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为1~m和1~n，Ai,j为1表示员工i能够制造产...
02014年4月27日4,991费用流