Floyd算法与数论简介

因为Floyd算法太简单了，所以和数轮简介放在一起。

Flody算法的思路与实现

Floyd算法是求多元最短路的利器。
就是时间复杂度吗……
emm，$O({n} ^ 3)$……
先说一下什么是多元最短路：
（划重点了！！！

多元最短路是指，可以求出任意两点之间最短距离的算法（这不就是DP嘛？

的确，Floyd算法就是基于$动态规划$实现滴！
既然是DP，那么我们就需要搬出思考DP最nb的思考方式：

闫式DP分析法。

关于下图，要特地感谢[@垫底抽风]大佬的分享和帮忙调试！！！

送给ta一个十连膜%%%%%%%%%%

$ Floyd： \left\\{ \begin{aligned} 状态表示： & \left\\{ \begin{aligned} & 集合——所有 & \\\ \\\ \\\ & 集合属性：Min因为是最短路，所以是Min \\\ \\\ \\\ & dist[i][j][k] \left \\{ \begin{aligned} i: &从第i个点 \\\ j: &到第j个点 \\\ k: &指经过1-k \\\ \end{aligned} \right. & \end{aligned} \right. \\\ \\\ \\\ \\\ 状态计算：& \left\\{ \begin{aligned} & dist[k, i, j]:计算目标，从i走到j经过1-k的最短路。 \\\ \\\ \\\ & 更新： \left\\{ \begin{aligned} & 从k-1转移：dist[k-1,i,j]:指经过1到k-1 \\\ \\\ & 加上： \\\ \\\ & dist[k-1][k][j]:指经过k-1条边从k走到j。 \\\ \end{aligned} \right. \end{aligned} \right. \end{aligned} \right. $

卡 的 要 死

我们可以通过类似于后面要讲的滚动数组优化01背包问题的方法优化Floyd。

优化后，Floyd算法的状态转移方程是：
$ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); $

然后来说一下如何一步一步的推出来$dist[i][j]$
我们可以直接进行三层循环，分别循环k，i，j，每一次搞一下状态转移方程就好了。
为了方便，我们把dist改成了d。

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

完了？

完了……

Floyd的实现与综合应用。

Floyd算法最常用的就是求传递闭包。
但是我们这里不讲。
（算是给大家留一个引子
请看这道题
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数n，m，k

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式
共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围
$ 1≤n≤200,\\\ 1≤k≤n^2\\\ 1≤m≤20000,\\\ $
图中涉及边长绝对值均不超过10000。

输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

impossible
1

我们这里加上一些Floyd算法的初始化与判断最短路是否无解。
初始化：

for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        if(i == j) d[i][j] = 0;//自己到自己的最短路为0
        else d[i][j] = 1e9;

然后读入时我们就把d当成邻接矩阵就好了。

while(m --)
{
    int a, b, c;
    cin >> a >> b >> c;
    d[a][b] = min(d[a][b], c);
}

判断是否无解不能直接用0x3f3f3f3f,

因为可能存在负权边！！！

if(d[a][b] > 1e9 / 2) puts("impossible");

所以这里改成了这样。
完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 210, X = 1e9;
int n, m, q, d[N][N];
int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = X;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    while(q --)
    {
        int a, b;
        cin >> a >> b;
        if(d[a][b] > X / 2) puts("impossible");
        else cout << d[a][b] << endl;
    }
}

作者：cht
链接：https://www.acwing.com/activity/content/code/content/336003/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

今天的重头戏！数论简介。

众所周知，各位大学生们拥有3打苦处：
$ \left\\{ \begin{aligned} 离散数学——一些自闭理论与证明 \\\ 组合数学——更多自闭理论与证明\\\ 高等数学——新的自闭理论与证明\\\ \end{aligned} \right. $
所以数论由此诞生！
我们会讲解如下这些内容：
（不会附链接！请大家实时关注！！！
1. 因倍质合（1）——小学奥数的噩梦
2. 因倍质合（2）——神奇的TLE
3. 欧几里得算法与拓展欧几里得算法——自闭的同余方程
4. 欧拉函数——xxs的妙用
5. 容斥原理——从自闭到更加自闭
6. 组合数烤串——算法大集合
7. 中国剩余定理——到底是剩下的定理还是神的定理
8. 博弈论（1）——好玩的证明
9. 博弈论（2）——SG函数是个好东西
10. 高斯消元——基本功很重要

快速幂以前已经讲过啦！！！！
这些课时的顺序可能会改变！！！

好了这期分享就到这里了。

今天熬夜到凌晨0点！

这是我的全部分享

bye~