最短路 - Page 2

PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-5b281a755ab39345991164/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-5b281a755ab43595240010/]poj1635.Subwaytreesystems树的同构，哈希[crayon-5b281a755ab48312509805/]poj2419.Forests暴力即可[crayon-5b281a755ab4e400368607/]poj1717.Dominoesdp水题[crayon-5b281a755ab53661185705/]poj2949.WordRings建图+分数规划[crayon-5b281a755ab59934444412/] ...
02015年5月14日1,798递推与动规,spfa,深度搜索,二分法,并查集,哈希表

UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-5b281a755b1f3749922126/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日2,322spfa,贪心,点分治,floyd
「BZOJ3931」[CQOI2015] 网络吞吐量
题意即题解最短路+网络流1A了赞233[crayon-5b281a755bbf7155581647/]
82015年4月7日3,125STL,dijkstra,最大流
[JSOI2010] 旅行
给定一张无向图,可以k次交换两条边边权，求1到n的最短路交换执行于求最短路之前，边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n，无视i条边边权的最短路，然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-5b281a755c4cd219454999/] ...
22015年3月23日2,033STL,spfa
「POJ2404」Jogging Trails
DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...
02015年1月2日1,946floyd,状压动规
「zoj2760」How Many Shortest Path
Givenaweighteddirectedgraph,wedefinetheshortestpathasthepathwhohasthesmallestlengthamongallthepathconnectingthesourcevertextothetargetvertex.Andiftwopathissaidtobenon-overlapping,itmeansthatthetwopathhasnocommonedge.So,givenaweighteddirectedgraph,asourcevertexandatargetvertex,weareinterestedinhowmanynon-overlappingshortestpathcouldwefindoutatmost.InputInputconsistsofmultipletestcases.Thefirs...
02014年12月27日1,685floyd,最大流
「BZOJ1486」[HNOI2009] 最小圈
题解分数规划，二分答案用dfs版的spfa判负环[crayon-5b281a755d967933544560/]
02014年12月23日3,647spfa,二分法
「BZOJ1922」[SDOI2010] 大陆争霸
Description在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。幻想历8012年1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。幻想历8012年3月2日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。幻想...
22014年12月22日3,865STL,dijkstra
「BZOJ2718 / 1143」[Violet 4] 毕业旅行
DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后，用n-二分图最大匹配数即为答案[crayon-5b281a7573a97553920279/] ...
02014年12月22日2,657floyd,最大流
NOI2010海拔
DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。小Z作为该市的市长，他根据统计信息得到...
02014年12月17日1,980STL,最小割,dijkstra
「BZOJ4016」[FJOI2014] 最短路径树问题
cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0：最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-5b281a756a095540654491/] ...
52014年12月15日5,009STL,dijkstra,点分治
「BZOJ1027」[JSOI2007] 合金
Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...
82014年12月9日4,529floyd,几何