搜索结果
查询Tags标签： 短路，共有 152条记录-
CF1450E Capitalism 题解
首先发现这个 \(|a_i-a_j|=1\) 的形式比较接近差分约束，稍微转化一下就是：\(-1\le a_i-a_j\le 1\) 且 \(a_i\neq a_j\)。于是你会发现 \(a_i\neq a_j\) 不是差分约束的条件。 换个角度。容易发现一条边相连的两个点一定奇偶性不同。考虑原图中若存在奇环，那么显然这是自…
2022/9/14 23:20:47 人评论 次浏览 -
最短路算法之 Dijkstra
部分内容参考了李煜东的《算法竞赛进阶指南》，在此声明。单源最短路径 单源最短路径问题，是说，给定一张有向图（无向图）\(G=(V,E)\) ,\(V\) 是点集，\(E\) 是边集，\(|V|=n\)，\(|E|=m\)，节点是 \([1,n]\) 之间的连续整数，\((x,y,z)\) 描述一条从 \(x\) 到 \(y\) 边…
2022/9/4 1:22:46 人评论 次浏览 -
【题解】P5304 [GXOI/GZOI2019]旅行者（dijkstra，图论，最短路）
【题解】P5304 [GXOI/GZOI2019]旅行者 一道利用 dijkstra 的很妙的图论题！ 加深了我对于 dijkstra 的理解。 （于是在做完这道题两天后的模拟赛中遇到了和它套路几乎一样的，我却甚至没有想到用最短路……） 所以写个题解记录一下吧。题目链接 [GXOI/GZOI2019]旅行者 - 洛…
2022/8/24 6:54:13 人评论 次浏览 -
1031 Rinne Loves Graph 求经过k个障碍到达n的最短路 分层图或最短路+dp
链接：https://ac.nowcoder.com/acm/contest/26077/1031来源：牛客网 题目描述Island 发生了一场暴乱！现在 Rinne 要和 Setsuna 立马到地上世界去。众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条…
2022/8/23 23:26:51 人评论 次浏览 -
1044 [HAOI2012]ROAD dijkstra递推求最短路径数+生成反向最短路拓扑图 计算以每个点为顶点，每条边上的最短路条数
链接：https://ac.nowcoder.com/acm/contest/26077/1044来源：牛客网 题目描述C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要…
2022/8/22 6:53:15 人评论 次浏览 -
java第六周学习情况
这个星期接到了要开学的消息，心情是非常慌张的，毕竟还没有学到多少东西。但确实是要开学了。心中说不出激动还是紧张，那就带着这种奇妙的情绪记录这次的学习吧 首先必然还是看了相关的程序，记没记下来是另外一说，但我确实是看了的。然后就是一些Java的知识，在这里我…
2022/8/7 1:22:43 人评论 次浏览 -
学习记录java
访问修饰符 public,private,protected,以及不写（默认）时的区别 定义：Java中，可以使用访问修饰符来保护对类、变量、方法和构造方法的访问。Java 支持 4 种不同的访问权限。 分类 private : 在同一类内可见。使用对象：变量、方法。 注意：不能修饰类（外部类）default…
2022/7/31 1:30:16 人评论 次浏览 -
暑假Java自学（5）
private : 在同一类内可见。使用对象：变量、方法。 注意：不能修饰类（外部类）default (即缺省，什么也不写，不使用任何关键字）: 在同一包内可见，不使用任何修饰符。使用对象：类、接口、变量、方法。protected : 对同一包内的类和所有子类可见。使用对象：变量、方法…
2022/7/31 1:30:15 人评论 次浏览 -
2022.7.30 做题记录
Luogu5122 Fine Dining G Present 7.0 不难想到先从 \(n\) 跑一遍最短路得到每个点 \(i\to n\) 的最短路长度 \(\text{dist}_i\)，然后新建一个点 \(S\)，对每个有干草的点 \(u\) 我们连边 \(S\to u\)，边权为 \(\text{dist}_u-\text{val}_u\)，其中 \(\text{val}\) 表示美…
2022/7/30 23:27:24 人评论 次浏览 -
dijkstra最短路算法（堆优化）
这个算法不能处理负环情况，请转到Floyd算法或SPFA算法（SPFA不能处理负环，但能判断负环） SPFA(SLF优化)：https://www.cnblogs.com/yifan0305/p/16391419.html 代码很长，耐下心来看完，存储方法为链式前向星存储。 (如果内存放得下的话，建议稠密图用邻接矩阵(或者跑f…
2022/7/23 1:26:25 人评论 次浏览 -
Dijkstra算法求最短路
例题链接 Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。其主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止 具体流程： 代码实现： #include<iostream>…
2022/7/14 1:26:05 人评论 次浏览 -
Java基础核心之运算符扩充
这里对日常开发中经常用到的运算符进行补充几种 一、移位运算符：我们经常在阅读源码中看到移位运算符的使用，简单来说主要就是对除法或乘法操作(针对于除以2或者乘以2的次数)进行简化1、移位运算符分类：1.1、左移运算符：箭头朝左，<<左移几位数就是该数乘以2…
2022/7/13 14:24:02 人评论 次浏览 -
算法提高课导读
搜索 DFS Flood Fill池塘计数 城堡问题 山峰和山谷最短路模型迷宫问题 武士风度的牛 抓住那头牛多源BFS矩阵距离最小步数模型魔板双端队列广搜电路维修双向广搜字串变换A*第K短路 八数码
2022/7/12 1:31:17 人评论 次浏览 -
平面图转对偶图
平面图转对偶图常用于解决平面图的最小割问题。 所谓平面图，就是能够在纸上画出来任意两边不在非顶点处相交的图。 对偶图是相对于一个平面图而言的。由于平面图的性质，你可以在纸上看到一些由边围成的许多封闭的面，假如把这些面编个号，看成节点，把两个面的交边映射到…
2022/7/8 23:53:12 人评论 次浏览 -
最短路常用算法
弗洛伊德(Floyd-Warshall) 时间复杂度\(O(n^3)\) 多元最短路，核心思想是依次将所有点作为中转点并更新所有路径。 核心代码也只有5行 for(int i=1;i<=n;++i)//外层循环一定是中转点for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)if(g[j][k]>g[j][i]+g[i][k])g[…
2022/7/4 1:21:34 人评论 次浏览
