floyd - hzwer.com

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

2016程序设计实习实验班免修考试(算法)
02:热血格斗场[crayon-673fbefbdd552640736394/]05:MPIMaelstrom[crayon-673fbefbdd55c626314438/]06:Ultra-QuickSort[crayon-673fbefbdd561066964678/]08:DrainageDitches[crayon-673fbefbdd566994647768/] ...
02017年2月10日6,324STL,floyd,最大流,树状数组
POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-673fbefbdda89986306377/]2728.DesertKing最优比率生成树分数规划[crayon-673fbefbdda94426316741/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-673fbefbdda...
02015年5月17日6,549STL,贪心,prim,二分法,floyd,树形动规,并查集,2-SAT
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-673fbefbde0d5521122166/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,298spfa,贪心,floyd,点分治
「POJ2404」Jogging Trails
DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...
02015年1月2日4,457floyd,状压动规
「zoj2760」How Many Shortest Path
Givenaweighteddirectedgraph,wedefinetheshortestpathasthepathwhohasthesmallestlengthamongallthepathconnectingthesourcevertextothetargetvertex.Andiftwopathissaidtobenon-overlapping,itmeansthatthetwopathhasnocommonedge.So,givenaweighteddirectedgraph,asourcevertexandatargetvertex,weareinterestedinhowmanynon-overlappingshortestpathcouldwefindoutatmost.InputInputconsistsofmultipletestcases.Thefirs...
02014年12月27日3,497floyd,最大流
「BZOJ2718 / 1143」[Violet 4] 毕业旅行
DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后，用n-二分图最大匹配数即为答案[crayon-673fbefbdf2ee621559101/] ...
02014年12月22日4,857floyd,最大流
「BZOJ1027」[JSOI2007] 合金
Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...
82014年12月9日6,509floyd,几何
「BZOJ2324」[ZJOI2011] 营救皮卡丘
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧...
02014年10月9日7,566费用流,floyd
「POJ1734」Sightseeing trip
DescriptionThereisatravelagencyinAdeltontownonZanzibarisland.Ithasdecidedtoofferitsclients,besidesmanyotherattractions,sightseeingthetown.Toearnasmuchaspossiblefromthisattraction,theagencyhasacceptedashrewddecision:itisnecessarytofindtheshortestroutewhichbeginsandendsatthesameplace.Yourtaskistowriteaprogramwhichfindssucharoute.InthetownthereareNcrossingpointsnumberedfrom1toNandMtwo-wayr...
02014年9月24日3,794floyd
「1612」[Usaco2008 Jan] Cow Contest奶牛的比赛
DescriptionFJ的N(1<=N<=100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1<=A<=N;1<=B<=N;A!=B)，那么她们的对决中，编号为A的奶牛总是能胜出。F...
02014年5月22日5,575floyd
「BZOJ1641」[Usaco2007 Nov] Cow Hurdles 奶牛跨栏
DescriptionFarmerJohn想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有N(1≤N≤300)个站台，分别标记为1..N。所有站台之间有M(1≤M≤25,000)条单向路径，第i条路经是从站台Si开始，到站台Ei，其中最高的栏的高度为Hi(1≤Hi≤1,000,0...
12014年4月16日3,732floyd