web analytics

Category Archives: spfa

NOIP2017模板复习.(救命系列)

救命系列.

[......]

阅读全文

USACO2017FEB Gold 解析报告

测试链接:http://usaco.org/index.php?page=feb17results
[......]

阅读全文

BZOJ 2330: [SCOI2011]糖果 差分约束

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2330
[......]

阅读全文

NOIP模拟赛-BZOJ3538-坑爹的GPS spfa

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 524288kB
描述
有一天,FJ买了一辆车,但是,他一手下载了两个GPS系统。好了现在麻烦的事情来了,GPS有一个功能大概大家也知道,如果FJ没有按照GPS内置地图的最短路走,GPS就会报错来骚扰你。现在FJ准备从[......]

阅读全文

POJ3159 差分约束系统

Description

During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class[......]

阅读全文

BZOJ1731[Usaco2005 dec]Layout 排队布局/差分约束系统

Description

Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1[......]

阅读全文

JZOJ.4826 小澳的葫芦 解题报告

Description
小澳最喜欢的歌曲就是《葫芦娃》。
一日表演唱歌,他尽了洪荒之力,唱响心中圣歌。
随之,小澳进入了葫芦世界。
葫芦世界有n个葫芦,标号为1~ n。n个葫芦由m条藤连接,每条藤连接了两个葫芦,这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫[......]

阅读全文

BZOJ1179 Atm //缩点+spfa

1179: [Apio2009]Atm

Description

Input

第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行,每行一个整数,按[......]

阅读全文

BZOJ1003 物流运输 最短路+DP

1003: [ZJOI2006]物流运输

Description

  物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候[......]

阅读全文

spfa-codevs1021题解

玛丽卡codes 1021

必备知识:spfa

题目描述 Description

麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复。

因为她和他们不住在同一个城市,因此她开始准备她的长途旅行。

在这个国家中每两个城市之间最多只有一条路相通,并且我们知道从一个城市到另一个城市路上所需花费的时[......]

阅读全文

裸裸的spfa~嘿嘿嘿!

裸裸的spfa~嘿嘿嘿!

spfa全名:shortest path faster algorithm ,又是一个国内神犇写的算法。

目的:一个图图,之后求图图从起点到终点的最短路径长度。

这种算法在效率上呢。!你不能质疑神犇的算法效率!但是这个算法不是很稳定。当然这种算法在稀疏图上是特别长脸的[......]

阅读全文