最大流 - Page 2

「网络流24题」最长递增子序列问题
题意有些奇怪任务（2）是取出。。。且题中递增是非严格递增我的代码任务3若能取出无限多的序列，则输出-1输入41324输出3 1 2样例2输入43625输出2 2 -1搬运byvoid神犇题解「问题分析」第一问是LIS，动态规划求解，第二问和第三问用网络最大流解决。「建模方法」首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到&...
52014年12月27日6,146最大流

「POJ1149」PIGS
DescriptionMirkoworksonapigfarmthatconsistsofMlockedpig-housesandMirkocan'tunlockanypighousebecausehedoesn'thavethekeys.Customerscometothefarmoneafteranother.Eachofthemhaskeystosomepig-housesandwantstobuyacertainnumberofpigs.AlldataconcerningcustomersplanningtovisitthefarmonthatparticulardayareavailabletoMirkoearlyinthemorningsothathecanmakeasales-planinordertomaximizethenumberofpigssold.M...
02014年12月27日5,411最大流
「CF498C」Array and Operations
Youhavewrittenonapieceofpaperanarrayofnpositiveintegersa[1], a[2], ..., a[n]andmgoodpairsofintegers(i1, j1), (i2, j2), ..., (im, jm).Eachgoodpair(ik, jk)meetsthefollowingconditions:ik + jkisanoddnumberand1 ≤ ik < jk ≤ n.Inoneoperationyoucanperformasequenceofactions:takeoneofthegoodpairs(ik, jk)andsomeintegerv(v > 1),whichdividesbothnumbersa[ik]anda[jk];dividebothnum...
02014年12月25日4,187最大流
「BZOJ2718 / 1143」[Violet 4] 毕业旅行
DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后，用n-二分图最大匹配数即为答案[crayon-662c282eda5a6505067075/] ...
02014年12月22日4,611最大流,floyd
「BZOJ1822」[JSOI2010] Frozen Nova 冷冻波
DescriptionWJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能FrozenNova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖，每个巫妖释放FrozenNova之后，都需要等待一段时间，...
62014年12月15日4,429二分法,最大流,几何
「BZOJ2929」[POI1999] 洞穴攀行
Description一队洞穴学者在ByteMountain的GrateCave里组织了一次训练。训练中，每一位洞穴学者要从最高的一个室到达最底下的一个室。他们只能向下走。一条路上每一个连续的室都要比它的前一个低。此外，每一个洞穴学者都要从最高的室出发，沿不同的路走到最低的室。问：可以有多少个人同时参加训练？任务：写一个程序：l 读入对洞穴的描述。l 计算可以同时参加训练的人数。l 将...
132014年12月9日3,881最大流
「codecomb2092」课程选择
题目描述大学选课总是烦恼着很多人。现在X同学选出了很多备选课，但是有的课程之间是有时间冲突的。X不会分身，自然无法在同一个时间上不同的课。每个课可能有很多备选时间，但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。现在把X的备选课及相应的上课时间告诉你，请你求出X一星期最多可以上多少课。输入格式第一行输入一个n，表示X将提供给你n个备选课。接下来n行，每行...
02014年10月13日2,581最大流
「codecomb2091」路径数量
题目描述给定一张n个点的有向图，求从点1到点n最多有多少条不相交的简单路径。所谓不相交即不经过相同的边的路径。输入格式第一行读入一个n，m，表示共n个点，m条边。接下来m行，每行两个整数x，y，表示从x到y有一条有向边。输出格式输出仅包括一行，即最多有多少条不相交的简单路劲。样例数据1输入4712122323233434输出2备注对于20%的数据n<=10，m<=1000；对于100%的数据n<=1000，m<=100000；题...
02014年10月13日2,980最大流
「BZOJ3396」[Usaco2009 Jan] Total flow 水流
DescriptionInput第1行输入N，之后N行每行描述一条水管，前两个英文字母表示水管的两端（大小写字母是不一样的），后一个整数表示水管的流量，流量不会超过1000.Output一个整数，表示总流量．SampleInput5AB3BC3CD5DZ4BZ6SampleOutput3题解直接上网络流模板。。。似乎有小写字母[crayon-662c282eeee83145158013/] ...
02014年7月10日3,507最大流
「NOIP模拟赛」魔术球问题弱化版
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4根柱子上最多可放11个球。对于给定的n，计算在n根柱子上最多能放多少个球。输入描述第1行有1个正整数n，表示柱子数。输出描述一行表示可以放的最大球数4样例输出。样例输入11题目限制（...
02014年7月3日3,152二分法,最大流
「BZOJ3504」[CQOI2014] 危桥
DescriptionAlice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？Input本...
22014年6月21日5,138最大流
「BZOJ1711」[Usaco2007 Open] Dingin吃饭
Description农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食.每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.农夫JOHN做了F(1<=F<=100)种食品并准备了D(1<=D<=100)种饮料.他的N(1<=N<=100)头牛都以决定了是否愿意吃某种食物和喝某种饮料.农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物...
02014年5月20日3,919最大流