网络流 - Page 6

「BZOJ2502」清理雪道
Description 滑雪场坐落在FJ省西北部的若干座山上。从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。由于每次飞行的耗费是固定的，为了最小化耗费，你想知...
02014年6月17日5,416有上下界网络流

「BZOJ2055」80人环游世界
DescriptionInput第一行两个正整数N，M。第二行有N个不大于M正整数，分别表示V1，V2......VN。接下来有N¡1行。第i行有N¡i个整数，该行的第j个数表示从第i个国家到第i+j个国家的机票费（如果该值等于¡1则表示这两个国家间没有通航）。Output在第一行输出最少的总费用。SampleInput632131212685082416104-14SampleOutput27HINT1<=N<=1001<=M<=79题解m个人的起始点任意。。。这什么奇怪的设定。...
02014年6月17日4,555有上下界网络流
「BZOJ1532」[POI2005] Kos – Dicing
DescriptionDicing是一个两人玩的游戏,这个游戏在Byteotia非常流行.甚至人们专门成立了这个游戏的一个俱乐部.俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.Input第一行两个整数n和m,1<=n<=10000,0<=m<=...
02014年6月15日3,894最小割,二分法
「BZOJ1930」[SHOI2003] pacman吃豆豆
Description两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。Input第一行为一个整数N，表示豆豆的数目。接下来N行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。O...
112014年6月14日5,718费用流
「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,548费用流
「POJ2396」Budget
DescriptionWearesupposedtomakeabudgetproposalforthismulti-sitecompetition.Thebudgetproposalisamatrixwheretherowsrepresentdifferentkindsofexpensesandthecolumnsrepresentdifferentsites.Wehadameetingaboutthis,sometimeagowherewediscussedthesumsoverdifferentkindsofexpensesandsumsoverdifferentsites.Therewasalsosometalkaboutspecialconstraints:someonementionedthatComputerCenterwouldneedatleast2000K...
12014年6月3日3,951有上下界网络流
「zoj3229」Shoot the Bullet
Gensokyo isaworldwhichexistsquietlybesideours,separatedbyamysticalborder.Itisautopiawherehumansandotherbeingssuchasfairies, youkai(phantoms),andgodslivepeacefullytogether.ShameimaruAyaisacrowtenguwiththeabilitytomanipulatewindwhohasbeenin Gensokyo forover1000years.SherunstheBunbunmaruNews-anewspaperchock-fullofrumors,andownsthe Bunkachou -herrecordofinterestingobservationsforBunbun...
22014年6月3日5,832有上下界网络流
「zoj2314」Reactor Cooling
TheterroristgroupleadedbyawellknowninternationalterroristBenBladenisbulidinganuclearreactortoproduceplutoniumforthenuclearbombtheyareplanningtocreate.Beingthewickedcomputergeniusofthisgroup,youareresponsiblefordevelopingthecoolingsystemforthereactor.Thecoolingsystemofthereactorconsistsofthenumberofpipesthatspecialcoolingliquidflowsby.Pipesareconnectedatspecialpoints,callednodes,eachpipehasth...
02014年6月3日5,170有上下界网络流
「NOIP模拟赛」密码锁
题目描述hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有...
42014年6月1日5,075费用流,广度搜索,状压动规,记忆化搜索
NOI2008志愿者招募
Description申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N天才能完成，其中第i天至少需要Ai个人。布布通过了解得知，一共有M类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天，招募费用是每人Ci元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，...
22014年5月31日4,605费用流
「BZOJ1711」[Usaco2007 Open] Dingin吃饭
Description农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食.每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.农夫JOHN做了F(1<=F<=100)种食品并准备了D(1<=D<=100)种饮料.他的N(1<=N<=100)头牛都以决定了是否愿意吃某种食物和喝某种饮料.农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物...
02014年5月20日3,949最大流
「BZOJ1458」士兵占领
Description有一个M*N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵,第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。Input第一行两个数M,N,K分别表示棋盘的行数，列数以及士兵的个数。第二行有M个数表示Li。第三行有N个数表示Ci。接下来有K行，...
02014年5月10日4,029最大流