首页 > 其他分享 >[学习笔记] 倍增 Floyd

[学习笔记] 倍增 Floyd

时间:2023-07-23 19:47:52浏览次数:42  
标签:matrix rep 矩阵 笔记 thxy cdots Floyd 倍增

一、朴素 Floyd

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

二、倍增 Floyd / 传递闭包

要做 \(k(\leq 10^9)\) 次 Floyd,怎么办?

将 Floyd 转化为广义矩阵乘法,直接跑矩阵快速幂,可以优化到 \(O(n^3\log k)\)。

三、P2886 Cow Relays G

首先先离散化,因为边数有 \(100\) 条所以点数最多 \(200\) 个。

传递闭包:先将初始临界矩阵 \(M\) 建立出来,\(M^k\) 就代表经过 \(k\) 条边的最短路;将其设为 \(0/1\)(有无边)可以求出任意两点之间的路径数。

四、P6569 [NOI Online #3 提高组] 魔法值

朴素的 40pts 做法:

第 \(i\) 天的魔法值的对应矩阵:

\[Mt_i=\begin{bmatrix}f_{1,i}&f_{2,i}&\dots&f_{n-1,i}&f_{n,i}\end{bmatrix} \]

转移方程,设 \(S_u\) 表示与 \(u\) 相邻的城市:

\[f_{u,i}=\bigoplus_{v \in S_u}f_{v,i-1} \]

设 \(T_{u,v}\) 表示 \(u\) 与 \(v\) 是否连通。

重载矩阵乘法:

\[A\times B=C \]

\[C_{i,j}=\bigoplus_{k=1}^{n}A_{i,k}B_{k,j} \]

转移矩阵:

\[M=\begin{bmatrix}T_{1,1}&T_{1,2}&\cdots&T_{1,n-1}&T_{1,n}\\T_{2,1}&T_{2,2}&\cdots&T_{2,n-1}&T_{2,n}\\\vdots&\vdots&\ddots&\vdots&\vdots\\T_{n-1,1}&T_{n-1,2}&\cdots&T_{n-1,n-1}&T_{n-1,n}\\T_{n,1}&T_{n,2}&\cdots&T_{n,n-1}&T_{n,n}\end{bmatrix} \]

\[Mt_{k}=Mt_{k-1}\times M \]

\[Mt_{k}=M t_0\times M^k \]

卡常后的 100pts 做法:

你还需要:亿点点信仰!&& O2 优化

  1. 矩阵乘法交换顺序,如:
matrix operator * (matrix A, matrix B) {
	matrix C;
	if (A.m == B.n) ; else swap (A, B);
	C.n = A.n, C.m = B.m;
	rep (i, 1, C.n) rep (j, 1, C.m) C.a[i][j] = 0;
	rep (i, 1, C.n) {
		rep (k, 1, A.m) {
			rep (j, 1, C.m) {
				C.a[i][j] ^= B.a[k][j] * A.a[i][k];
			}
		}
	}
	return C;
}
  1. 预处理矩阵的 \(2\) 次方幂:
thxy[0] = M;                                       
rep (i, 1, 32) thxy[i] = thxy[i - 1] * thxy[i - 1];
  1. 使用位运算计算:
for (int j = 1, _ = 0; j <= ai; j <<= 1, ++ _) {
	if ((ai & j)) mxp = flag ? mxp * thxy[_] : thxy[_], flag |= 1;
} 	

标签:matrix,rep,矩阵,笔记,thxy,cdots,Floyd,倍增
From: https://www.cnblogs.com/RB16B/p/17575748.html

相关文章

  • LSM树学习笔记
    LSM-Tree即logstructuredmergetree。LSM-Tree是许多高度可扩展的NoSQL分布式键值类型数据库(如亚马逊的DynamoDB、Cassandra和ScyllaDB)的基础数据结构。众所周知,这些数据库在设计上支持的写入率远远超过传统关系数据库所能提供的写入率。几乎所有NoSQL数据库都使用LSM树的变体......
  • [c/c++][考研复习笔记]排序篇学习笔记
    考研排序复习笔记插入排序#include<stdio.h>#include<stdlib.h>#defineMaxSize9//折半插入排序voidZBInsertSort(intA[],intn){ inti,j,high,low,mid; for(i=2;i<=n;i++){ A[0]=A[i]; low=1;high=i-1; while(low<=high){ mid=(low+high)/2......
  • PMP 学习笔记(七)
    07.18星期二CPI0.65——成本偏差较大,使用自下而上的估计出现新的干系人,应更新干系人登记册,敏捷方法由产品经理列入待办事项凸显模型适用于复杂的干系人大型社区审查可交付成果,干系人表现出对最终产品的担忧,按时可交付成果有问题,应审查项目需求文件产品不合格,根本原因是开发......
  • 笔记-C-typdef定义数组
    typdef定义数组后的初始化|计算机内部只知晓地址,类型为上层的高级语义#include<stdio.h>typedefintARR_INT_2[2];voidtest(ARR_INT_2*t){int*t1;int*t2;t1=&(((int*)t)[0]);t2=&(((int*)t)[1]);printf("t1addr-%p\n",t1);......
  • css 笔记
    一、inline-block与overflow:hidden的冲突inline-block元素设置overflow:hidden后,其本身会上移解决方法:在该元素或其父元素上设置  vertical-align:bottom;原因解释:inline-block元素被设置oveflow非visible后,其baseline被强制修改为元素下外边沿,该元素将底部......
  • 搜索笔记
    搜索双向搜索双向同时搜索定义:双向同时搜索的基本思路是从状态图上的起点和终点同时开始进行BFS和DFS。如果发现搜索的两端相遇了,那么可以认为是获得了可行解。模版实现:if(start==finish)return0;初始化visited数组里每个值为0;//这里visited值为1则为向后搜......
  • 3b1b 线性代数本质 学习笔记
    导航向量基向量特征向量矩阵行列式逆矩阵矩阵与方程组秩满秩列空间零空间核点积叉积基变换向量空间中的箭头\(\vec{v}\)可以自由移动/一般以原点为起点有序的数字列表\(\begin{bmatrix}a\\\vdots\\b\end{bmatrix}\)相加相乘有意义的东西......
  • C#学习笔记 —— LINQ
    LINQ1、什么是LINQ使用LINQ可以轻松查询对象集合LINQ代表语言集成查询LINQ是.NET框架的扩展,允许我们使用SQL查询数据库的类似方式来查询数据集合LINQ可以从数据库、对象集合、XML文档中查询数据2、LINQ提供程序对于每一种数据源类型,一定有根据该数据源类型实现LI......
  • 在尚硅谷学习docker 笔记
    尚硅谷docker学习笔记1.docker简介(基础篇)2.docker的安装3.docker的常用命令3.1帮助启动类命令3.2镜像命令3.3容器命令4.对docker镜像的深入理解4.1镜像的一些重要概念4.2docker镜像commit操作案例4.3本地镜像发布到阿里云/私有库5.docker容器数据卷(实现持久......
  • 公司财报分析(读书笔记)
    一、财报财报:一般分为一季报、半年报(中报)、三季报(三季报)、年报(年报)四种。我国上市公司一般每年四次披露财务报表,分别是一季报、中报、三季报和年报。一季报和三季报是未经审计的财务报表,中报和年报是经审计的财务报表。季报和年报区别:季报是未经审计的财务报表,年报是经审......