whust 2016 warm up E ||codeforces 689 B. Mike and Shortcuts (spfa)

cf689B题目链接

题意:n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1(注意近路不一定就近)

思路:一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2*N蠢哭。。。实际上应该3*M…因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

 

 

 

 

BZOJ 1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明 (spfa)

1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 250  Solved: 178
[Submit][Status][Discuss]

Description

A crime has been comitted: a load of grain has been taken from the barn by one of FJ’s cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. NOTE: Do not declare a variable named exactly ‘time’. This will reference the system call and never give you the results you really want.

    谷仓里发现谷物被盗!约翰正试图从C(1≤C≤100)只奶牛里找出那个偷谷物的罪犯.幸运的是,一个恰好路过的卫星拍下谷物被盗前M(1≤M≤70000)秒的农场的图片.这样约翰就能通过牛们的位置来判断谁有足够的时间来盗窃谷物.
    约翰农场有F(1≤F≤500)草地,标号1到F,还有P(1≤P≤1000)条双向路连接着它们.通过这些路需要的时间在1到70000秒的范围内.田地1上建有那个被盗的谷仓. 给出农场地图,以及卫星照片里每只牛所在的位置.请判断哪些牛有可能犯罪.

Input

* Line 1: Four space-separated integers: F, P, C, and M * Lines 2..P+1: Three space-separated integers describing a path: F1, F2, and T. The path connects F1 and F2 and requires T seconds to traverse. * Lines P+2..P+C+1: One integer per line, the location of a cow. The first line gives the field number of cow 1, the second of cow 2, etc.

第1行输入四个整数F,只C,和M;

接下来P行每行三个整数描述一条路,起点终点和通过时间.

接下来C行每行一个整数,表示一头牛所在的地点.

Output

* Line 1: A single integer N, the number of cows that could be guilty of the crime.

* Lines 2..N+1: A single cow number on each line that is one of the cows that could be guilty of the crime. The list must be in ascending order.

    第1行输出嫌疑犯的数目,接下来一行输出一只嫌疑犯的编号.

Sample Input

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

Sample Output

4
1
2
3
4

HINT

 

思路: 非常显然的最短路。。。。一个月没写代码还能1A…感动

 

 

uva 10986 Sending email (spfa)

uva10986题目链接
题意:裸的spfa.

思路:模板,1A.

 

poj 2949 Word Rings (spfa+栈优化)

poj2949 题目链接
题意:我们有 n 个 (n<=100000) 字符串,每个字符串都是由 a~z 的小写英文字
母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两字符相
匹配,那么我们称 A 与 B 能相连(注意: A 能与 B 相连不代表 B 能与 A 相连)。
我们希望从给定的字符串中找出一些,使得他们首尾相接形成一个环串(一个串首尾相连也算)
我们想要使这个环串的平均长度最长。

思路:参考了国家集训队论文《spfa算法的优化与应用》

首先我卡在了关于接龙问题的处理方法,只能想到n^2的方法。。显然gg.

而正解是把每个单词看做一条边,把每个单词开头的两个字母和结尾两个字母看做起点和终点,由于都是小写字母,2位26进制数最多表示26*26。

这个建图方式并不是特别显然,不过想一下还是可以理解的。。以及这应该算是处理单词接龙问题的一个技巧。。。

 

这道题综合了两种常见的问题:字符串的接龙以及平均值的最优化问题。对于前者,我们可以采取把单词看成边,把首尾字母组合看成点的方法。例如对于单词ababc就是点”ab”向点”bc”连一条长度为5的边。这样问题的模型变得更加清晰,规模也得到减小。那么原问题就可以转化成在此图中找一个环,使得环上边权的平均值最大。对于这种问题,我们有很经典的解决方法:

由于Average=(E1+E2+…..+Ek)/K
所以Average*K=E1+E2+……+Ek
即(E1-Average)+(E2-Average)+….+ (Ek-Average)=0
另外注意到上式中的等于号可以改写为小于等于,那么我们可以二分答案Ans,然后判断是否存在一组解满足(E1+E2+…..+Ek)/K>Ans,即判断
(E1- Ans)+(E2- Ans)+….+ (Ek- Ans)>0
于是在二分答案后,我们把边的权值更新,问题就变成了查找图中是否存在一个正环。

 

然后参考了这篇题解学习了一下栈优化的spfa: spfa栈优化   

以及这篇博客中比较了dfs的spfa和普通栈优化的spfa… 200+ms vs 2000+ms…十倍的优化。。太神了。。。

 

/*
枚举每一个平均长度mid值。
如果存在一个环,(E1+…+Ek)/k>=mid(其中k是边数,E1……Ek是各个边权),
那么正解比mid大,否则比mid小,这就是二分策略。
那么怎样知道是否存在(E1+…+Ek)/k>=mid 呢?
如下转化:(E1+…+Ek)>=mid*k
E1-mid + E2–mid + E3-mid + … + Ek-mid >= 0
所以,把所有的边权改为Ei – mid,然后看是否存在正环就可以,存在就是满足条件。
*/

 

 

poj 1860 Currency Exchange (spfa求最长路)

poj 1860 题目链接

题意:有n种货币,m个货币交易点,每个货币交易点只能是两种货币之间交换,给出两个方向的汇率和手续费。初始拥有数量v的货币s,问能否经过一些py交易,使得最后手里的货币s比v多。

思路:大概还是用spfa求最长路。。松弛那里需要注意一下算法。。。

1A。。。好爽啊。。。。。

 

poj 1932 XYZZY (floyd传递闭包+spfa求最长路)

poj1932题目链接

题意:初始在点1,有100点能量,然后每个点有一个能量值【-100,100】,经过某个点会加上这个点的能量值,问能否找到一条到点n且的路线,且路径任何点的能量值一直为正。一共不超过100个点。

 

思路:像样例中是直接联通,一路上的能量值都大于0,这是有解的一种情况。另一种是存在一个正环,可能一次路过后面的能量值不够,但是我们可以走多次啊。

因为要求每一步的能量值都大于0,那么我们可以初始化d[]数组为0,然后用spfa求最长路(只需要把那个三角形等式换个方向即可)

如果可以直接联通,也就是d[n]>0,那么有解。

还有可能是存在一个环(判断环的方法是用一个数组在spfa的时候统计每个点入队的次数,如果一个点的入队次数大于n,那么就存在环,且这个点在环中

但是我们还要保证起点1和终点n是经过这个环的。

所以先跑一发floyd. 其实n才100也算给了提示吧,不用floyd的话没道理这么小的数据。。?

感觉这道题很棒,把spfa和floyd结合在了一起。

学到了判断环的方法,spfa求最长路的方法,复习了传递闭包。

 

 

 

 

poj 1511 Invitation Cards (链式前向星存图+spfa)

poj 1511 题目链接
题意:和那道奶牛的舞会类似,要求所有点到点1的距离和加上1点到所有点的距离和。
思路:正反存边建两次图,跑两次spfa. 然而用vector会TLE….所以去学习了新的建图方式。。。也就是链式前向星:链式前向星(边表)学习链接 也叫边表。

是一种几乎没有什么缺点的存图方式。。。? 比起普通的前向星少了个排序。

哦,还有我发现貌似很多人把这个东西叫邻接表。。但是根据这里:几种建图方式

这个东西还是交边表或者链式前向星比较合适。。。?

 

 

BZOJ 1614: [Usaco2007 Jan]Telephone Lines架设电话线 (二分+spfa)

1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1325  Solved: 570
[Submit][Status][Discuss]

Description

Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务。于是,FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线,其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i,它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i,B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络,整个农场的电话线全都连到了编号为N的电话线杆上。也就是说,FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。 经过谈判,电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线,FJ需要为它们付的费用,等于其中最长的电话线的长度(每根电话线仅连结一对电话线杆)。如果需要连结的电话线杆不超过 K对,那么FJ的总支出为0。 请你计算一下,FJ最少需要在电话线上花多少钱。

Input

* 第1行: 3个用空格隔开的整数:N,P,以及K

* 第2..P+1行: 第i+1行为3个用空格隔开的整数:A_i,B_i,L_i

Output

* 第1行: 输出1个整数,为FJ在这项工程上的最小支出。如果任务不可能完成, 输出-1

Sample Input

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输入说明:

一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。

Sample Output

4

输出说明:

FJ选择如下的连结方案:1->3;3->2;2->5,这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线,于是,
他所需要购买的电话线的最大长度为4。

HINT

 

思路:一开始把电话线条数和长度分别作为第一第二关键字,然后spfa.然后记录路径,找k个最大的以后的中最长的电话线就是答案。发现样例就是反例。。智力-2.

正确的做法是二分电话线的最大长度,大于最大长度的电话线交给电信公司取搞,看交给电信公司搞的电话线数目是否小于等于k.

二分的功夫还是不到家呀。。想不到。。
不过这道题和那个中国印度被喜马拉雅山脉阻隔,二分+bfs判断连通性的题目有点类似呢。

 

BZOJ 1631: [Usaco2007 Feb]Cow Party (SPFA)

1631: [Usaco2007 Feb]Cow Party

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 670  Solved: 493
[Submit][Status][Discuss]

Description

    农场有N(1≤N≤1000)个牛棚,每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对.共有M(1≤M≤100000)条单向路连接着牛棚,第i条踣需要Ti的时间来通过.牛们都很懒,所以不管是前去X牛棚参加派对还是返回住所,她们都采用了用时最少的路线.那么,用时最多的奶牛需要多少时间来回呢?

Input

第1行:三个用空格隔开的整数.

第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.

Output

唯一一行:一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

10

HINT

样例说明:
共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.
第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.

思路:想了一下。。因为要知道每个点到x的最短距离。。。以及反过来。。

单向很容易知道。。。以x点为起点做一遍spfa,那么x到每个点的最短距离就知道了。。

那么反过来怎么办呢?

我的做法是反向建边再跑一遍spfa…

1A,开心。

 

 

hdu 3790 最短路径问题 (spfa模板题)

hdu 3790 题目链接

题意:给出n个点m条无向边,每条边有一个距离和一个花费。给出s,t。问从s到t的最短距离以及最短距离时的最小花费。当有多个距离最短的方案时,选取花费最少的。

 

spfa学习链接

usetc 每周算法讲堂之spfa

 

先写几道题加深理解。

 

 

记得初始化。。。。。。