单源点最长路

2023-10-20 03:08

文章标签 最长源点

本文主要是介绍单源点最长路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短路算法总结

1.dijkstra

单源点最短路
思想：每次取到源点最短的点，因为没有负边，所以不能再被其它点优化

所以该图不能有负边，可以有环

2.贝尔曼福德

可以用负边，当不能有负环路，如果有负环路，会一直松弛下去，没有最短路

负环路:环路权重之和为负数

3.ford 多源点最短路

动态规划
可以有负权边
负权环是不是求不出最短路

单源点最长路
把边改为负边，然后继续用原来的算法求最短路即可

1.dijkstra 不能通过边权为负来求最长路
样例，以A为起点，A-D的边先出堆，所以D的边权先被确定了，无法被C再优化

spfa,ford可以
但图中不能有环,不然就会有负权环

这篇关于单源点最长路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/244197。 23002807@qq.com

相关文章

poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

阅读更多...

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。因为数据量比较大，用原来的O（n^2）会爆。小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

阅读更多...

hihocoder1050 : 树中的最长路

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述上回说到，小Ho得到了一棵二叉树玩具，这个玩具是由小球和木棍连接起来的，而在拆拼它的过程中，小Ho发现他不仅仅可以拼凑成一棵二叉树！还可以拼凑成一棵多叉树——好吧，其实就是更为平常的树而已。但是不管怎么说，小Ho喜爱的玩具又升级换代了，于是他更加爱不释手（其实说起来小球和木棍有什么好玩的是吧= =）。小Ho手

阅读更多...

POJ1631最长单调递增子序列

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

阅读更多...

计蒜客 Skiing 最长路

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the

阅读更多...

PHP最长单一子串

PHP最长单一子串

<?php//方法一$s='abcccddddddcdefg';$max='';while($s!=''){$i=0; while($i<strlen($s) && $s[$i]==$s[0]) $i++;if ($i>strlen($max)){$max=substr($s,0,$i);} $s=substr($s,$i);}echo $m

阅读更多...

day-50 求出最长好子序列 I

day-50 求出最长好子序列 I

思路二维dp,dp[i][h]表示nums[i] 结尾，且有不超过 h 个下标满足条件的最长好子序列的长度（0<=h<=k），二维数组dp初始值全为1 解题过程状态转换方程： 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1

阅读更多...

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接题目描述给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中最多只有 k 个下标i满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。实例1: 输入：nums = [1,2,1,1,3],

阅读更多...

Leetcode面试经典150题-128.最长连续序列-递归版本另解

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本可以看看之前的版本，两个版本面试用哪个都保过解法都在代码里，不懂就留言或者私信 class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的

阅读更多...

【UVA】10066-The Twin Towers（最长公共子串问题）

【UVA】10066-The Twin Towers（最长公共子串问题）

赤裸裸的最长公共子串问题，没什么好说的，注意的是，每组数据后面都有一个空行。 13996019 10066 The Twin Towers Accepted C++ 0.015 2014-08-06 00:34:53 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using

阅读更多...