首页 > 其他分享 >重做 CF 295B Greg and Graph 以及理解 Floyd

重做 CF 295B Greg and Graph 以及理解 Floyd

时间:2023-07-28 19:44:53浏览次数:40  
标签:Graph 路径 CF 295B Floyd dp mathrm

Floyd 原理简析

Floyd 的原理其实是 DP,定义 \(\mathrm{dp}[S][i][j]\) 表示在仅经过点集 \(S\) 里的点的条件下,从 \(i\) 到 \(j\) 的最短路距离

初始状态 \(S\) 为空,\(\mathrm{dp}[\varnothing ][i][j]\) 就等于 \(i,j\) 间的边长,没有边就是正无穷

转移方程,在加入一个新的点 \(k\) 的时候,

\[\mathrm{dp}[S+k][i][j] = \max\{ \mathrm{dp}[S][i][j], \mathrm{dp}[S][i][k] + \mathrm{dp}[S][k][j]\} \]

也就是说,每一次状态转移都是选取一个新点 \(k\),然后枚举所有的路径进行更新:将路径 \(<i, j>\) 拆成了 \(<i, k>,<k,j>\) 两段,比较这个有新点的路径是不是更优的,择优更新

因为每次更新之前 \(\mathrm{dp}[S][...][...]\) 都是已知的(要么是无法到达的 inf,要么是当前最优的答案),所以往后推每一次都是最优的

对于某一条最短路径 \(<i, j, k, l>\) ,虽然它在初始状态是无法联通的,但是随着新点的加入,\(<i, j, k>, <j, k, l>\) 终将联通,最后无论选择 \(j\) 还是 \(k\) 都能让 \(<i, j, k, l>\) 联通,只需选择最短的一条就可以得出答案了

写成代码的话一般都是按标号顺序更新点集,也就是 \(\mathrm{dp}[k][i][j]\) 表示考虑前 \(k\) 个点时的最短路径

然后再滚动掉第一维,就成了我们最后看到的样子:

int dist[MAXN][MAXN];

for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

CF 295 B Greg and Graph

看完上面的原理,为什么要倒序跑 Floyd 就很显然了,Floyd 的原理本来就是加点,放在这题自然再合适不过

标签:Graph,路径,CF,295B,Floyd,dp,mathrm
From: https://www.cnblogs.com/handwer/p/17588758.html

相关文章

  • CF547D Mike and Fish 小丑做法--zhengjun
    写到一半发现标签有二分图就不对劲了,题解区里都是欧拉回路。然而我是随机化+模拟网络流!自豪首先可以先建模,观察同一种颜色,发现每一行或每一列的限制即为\(\lfloor\frac{t}{2}\rfloor\lex\le\lceil\frac{t}{2}\rceil\)。然后套路地把横坐标和纵坐标分开来建个二分图,建立源点......
  • CF1851 A-G
    linkA非常简单的比较大小问题#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<set>#include<map>#include<ctime>#include&l......
  • CF1635E Cars
    题意:给定m对汽车之间的关系(无关紧要或命中注定·)。无关紧要:无论两辆汽车的速度是多少都不会相遇。命中注定:无论两辆汽车的速度是多少都一定会相遇。对每辆车给出一个行驶方向和起点使得m个关系成立。思路:首先我们考虑无关紧要可以证明,如果两车同向,只要让较后的车速度更快一......
  • 数字化时代,企业研发效能跃升之道丨IDCF
    本文节选自新书《数字化时代研发效能跃升方法与实践》作者:冬哥研发效能是近年的热词,企业言必谈效能,但究竟什么是研发效能,落地具体应该如何进行,相信每个人都会有无数的问题浮现。什么是效能?效能指的是个人、组织或系统在完成任务或达成目标时,所展现的能力和效率。具体而言,效能是指所......
  • CF623E Transforming Sequence
    难点在于卡__int128(?)。首先\(N>K\)显然无解,只需考虑\(N\leK\)的情况。然而这并没有什么用。把\(b\)看作集合,显然\(b_i\subsetb_{i+1}\)。所以令\(f_{n,i}\)为考虑到\(b_n\)且\(|b_n|=i\)的方案数,集合元素无序,即选择\(\{A,B,C\}\)或者\(\{A,B,D\}\in\{A,B,C,D......
  • MFC-文件操作CFile
             ......
  • CF938G Shortest Path Queries 题解
    目录题目链接题目分析为什么使用生成树建树对于异或贡献的分析code题目链接CF938G洛谷挂了只能交CF题目分析本题有以下几个关键点:为什么使用生成树建树首先根据\(WC2011\)我们发现可以使用\(dfs\)序来保存节点之间的关系但是我们发现本题目中存在加边删边操作不......
  • CF1053E-Euler Tour题解
    前言还是一道神仙题很难想题面luogu上copy的样例解释懒得翻,我觉得应该都看得懂样例吧。题面翻译现有一棵\(n\)个点的形态未知的树,给定其长度为\(2n-1\)的欧拉序的一部分请根据给出的残缺的欧拉序还原出一个完整的欧拉序或判断不存在这样的树输入中用非零数字表示欧拉......
  • ugui源码阅读 - Graphic渲染原理
    3d部分使用MeshRenderer来渲染,ugui的使用CanvasRenderer来进行渲染。把顶点,材质,贴图设置给CanvasRenderer,就能渲染出来了。 下面的代码,我们直接使用CanvasRenderer来进行渲染,等同于Graphic渲染部分的核心代码。usingUnityEngine;usingUnityEngine.UI;[RequireComponent(......
  • API架构的选择,RESTful、GraphQL还是gRPC
    API架构的选择,RESTful、GraphQL还是gRPC hi,我是熵减,见字如面。在现代的软件工程中,微服务或在客户端与服务端之间的信息传递的方式,比较常见的有三种架构设计的风格:RESTful、GraphQL和gRPC。每一种模式,都有其特点和合适的使用场景,今天,我们主要来对三种风格做一个深入的理解......