最短路 - Page 2

「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-67a300862813a941565795/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-67a3008628145419917993/]C.LevkoandStringsf(i,j)表示前i个字母，beauty值为j的合法方案，\(t_k=s_k\)(k>j)1.在第i位放一个比s[i]大的字母，枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)产生的新的bea...
12015年6月23日4,991递推与动规,贪心,spfa,二分法,最大公约数与最小公倍数

「CF545X」Codeforces Round #303 (Div. 2)
A.ToyCars模拟[crayon-67a300862890a594279130/]B.EquidistantString[crayon-67a3008628914192324534/]C.Woodcutters给n棵树在一维数轴上的坐标，以及它们的高度。现在要你砍倒这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然也不能覆盖其他的树原来的位置，现在求最大可以砍倒的树的数目。题解第一棵树的左边和最后一棵树的右边没树，所以他们向两边倒，然后对于中间的树来说，首先先向左边倒，然后左边...
12015年5月20日4,593模拟,STL,贪心,dijkstra
POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-67a300862bf71381945000/]2728.DesertKing最优比率生成树分数规划[crayon-67a300862bf7e802762114/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-67a300862bf...
02015年5月17日6,727STL,贪心,prim,二分法,树形动规,floyd,并查集,2-SAT
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-67a300862c65b915214297/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-67a300862c664813070199/]poj1635.Subwaytreesystems树的同构，哈希[crayon-67a300862c669423746227/]poj2419.Forests暴力即可[crayon-67a300862c66f055738269/]poj1717.Dominoesdp水题[crayon-67a300862c675325115761/]poj2949.WordRings建图+分数规划[crayon-67a300862c67b051559183/] ...
02015年5月14日4,133递推与动规,spfa,深度搜索,二分法,并查集,哈希表
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-67a300862cc89384349927/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,444spfa,贪心,floyd,点分治
「BZOJ3931」[CQOI2015] 网络吞吐量
题意即题解最短路+网络流1A了赞233[crayon-67a300862d633689260898/]
82015年4月7日5,711STL,dijkstra,最大流
[JSOI2010] 旅行
给定一张无向图,可以k次交换两条边边权，求1到n的最短路交换执行于求最短路之前，边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n，无视i条边边权的最短路，然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-67a300862df6b046499225/] ...
22015年3月23日3,970STL,spfa
「POJ2404」Jogging Trails
DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...
02015年1月2日4,600floyd,状压动规
「zoj2760」How Many Shortest Path
Givenaweighteddirectedgraph,wedefinetheshortestpathasthepathwhohasthesmallestlengthamongallthepathconnectingthesourcevertextothetargetvertex.Andiftwopathissaidtobenon-overlapping,itmeansthatthetwopathhasnocommonedge.So,givenaweighteddirectedgraph,asourcevertexandatargetvertex,weareinterestedinhowmanynon-overlappingshortestpathcouldwefindoutatmost.InputInputconsistsofmultipletestcases.Thefirs...
02014年12月27日3,601floyd,最大流
「BZOJ1486」[HNOI2009] 最小圈
题解分数规划，二分答案用dfs版的spfa判负环[crayon-67a3008646cfd232884488/]
02014年12月23日6,039spfa,二分法
「BZOJ1922」[SDOI2010] 大陆争霸
Description在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。幻想历8012年1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。幻想历8012年3月2日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。幻想...
22014年12月22日6,220STL,dijkstra
「BZOJ2718 / 1143」[Violet 4] 毕业旅行
DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后，用n-二分图最大匹配数即为答案[crayon-67a300864773d087319007/] ...
02014年12月22日4,986floyd,最大流