spfa - hzwer.com

PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-68a7f5c9a8166480466905/]POJ1860CurrencyExchange最短路模板[crayon-68a7f5c9a8178072166656/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
02019年12月29日6,427STL,spfa,后缀数组,并查集,线段树,图的连通

「省选模拟赛」[BZOJ1556] 小奇走迷宫
原题：「bzoj1556」墓地秘密「题目背景」小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫，一旁的木牌上写着：“你可以回头，但你永远无法离去。”「问题描述」木牌下方有一行小字：“撞击所有机关墙”。G-1500机器人每次可以朝着前方光速移动，质量、动能无穷大，可以选择自己在行进中停下来或者撞墙后停下来，移动时只有转向需要花费时间。真是个诡异的迷宫，不过，小奇的眼前已经出现了迷宫的地图，它想尽早离开这里，请你...
22015年12月19日7,809spfa,状压动规
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-68a7f5c9ac625917776298/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-68a7f5c9ac631746883273/]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日5,355递推与动规,贪心,spfa,二分法,最大公约数与最小公倍数
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-68a7f5c9ace15277251085/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-68a7f5c9ace1e927619195/]poj1635.Subwaytreesystems树的同构，哈希[crayon-68a7f5c9ace23650857976/]poj2419.Forests暴力即可[crayon-68a7f5c9ace29449340490/]poj1717.Dominoesdp水题[crayon-68a7f5c9ace2f321030275/]poj2949.WordRings建图+分数规划[crayon-68a7f5c9ace35417781995/] ...
02015年5月14日4,380递推与动规,spfa,深度搜索,二分法,并查集,哈希表
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-68a7f5c9adbc1337668417/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,713spfa,贪心,点分治,floyd
[JSOI2010] 旅行
给定一张无向图,可以k次交换两条边边权，求1到n的最短路交换执行于求最短路之前，边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n，无视i条边边权的最短路，然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-68a7f5c9aee56645103834/] ...
22015年3月23日4,177spfa,STL
「BZOJ1486」[HNOI2009] 最小圈
题解分数规划，二分答案用dfs版的spfa判负环[crayon-68a7f5c9af965955988124/]
02014年12月23日6,432spfa,二分法
「NOIP模拟赛」长途旅行
「题目描述」JY是一个爱旅游的探险家，也是一名强迫症患者。现在JY想要在C国进行一次长途旅行，C国拥有n个城市(编号为0,1,2...,n-1)，城市之间有m条道路，可能某个城市到自己有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。JY从0号城市开始出发，目的地为n–1号城市。由于JY想要好好参观一下C国，所以JY想要旅行恰好T小时。为了让自己的旅行更有意思，JY决定不在任何一个时刻停留(走...
42014年11月3日5,855spfa
「NOIP模拟赛」小奇回地球
原题目名：时间与空间之旅2015.9.13日hzwer重制了题面与数据「题目背景」开学了，小奇在回地球的路上，遇到了一个棘手的问题。「问题描述」简单来说，它要从标号为1的星球到标号为n的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。宇宙法规定：“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置，...
32014年10月28日5,799spfa,二分法
「BZOJ2304」[APIO2011] 寻路path
DescriptionTooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的，它们是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西走向，或者是南北走向。因为Dees是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，...
02014年8月5日7,527模拟,spfa,dijkstra,线段树
「BZOJ2100」[Usaco2010 Dec] Apple Delivery
DescriptionBessiehastwocrispredapplestodelivertotwoofherfriendsintheherd.Ofcourse,shetravelstheC(1<=C<=200,000)cowpathswhicharearrangedastheusualgraphwhichconnectsP(1<=P<=100,000)pasturesconvenientlynumberedfrom1..P:nocowpathleadsfromapasturetoitself,cowpathsarebidirectional,eachcowpathhasanassociateddistance,and,bestofall,itisalwayspossibletogetfromanypasturetoanyotherpasture....
02014年7月29日4,425spfa
「BZOJ2015」[Usaco2010 Feb] Chocolate Giving
DescriptionFarmerJohn有B头奶牛(1<=B<=25000)，有N(2*B<=N<=50000)个农场，编号1-N，有M(N-1<=M<=100000)条双向边，第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N)，它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B，但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物，...
02014年7月29日4,582spfa