零基础学算法100天第3天——Floyd(多源最短路径算法)(下)

简介: 零基础学算法100天第3天——Floyd(多源最短路径算法)

2.牛奶工厂        


image.png

     

题目链接:牛奶工厂https://www.acwing.com/problem/content/1473/        


题目分析:


        如果明白了上一道题,那么这道题也会马上明白思路,因为做法是完全一模一样的。我们直接写上状态表示和转移方程就能明白了。        


状态表示
    f[i][j]=true说明从i能走到j
    static boolean[][] f=new boolean[N][N];
    转移方程:
    //同理如果能找到一条从i到k,再从k到j,说明能从i到j
    f[i][j]|=(f[i][k]&&f[k][j]);

       代码转换:


import java.util.Scanner;
public class Main {
    static int N=110;
    //f[i][j]=true说明从i能走到j
    static boolean[][] f=new boolean[N][N];
    static int n;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for (int i = 0; i < n-1; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            f[a][b]=true;
        }
        for (int k = 1; k <=n; k++) {
            for (int i = 1; i <=n; i++) {
                for (int j = 1; j <=n; j++) {
                    f[i][j]|=(f[i][k]&&f[k][j]);
                }
            }
        }
        for (int i = 1; i <=n; i++) {
            int res=0;
            for (int j = 1; j <=n; j++) {
                //注意我们找的是能从其他点都能到i点
                if (f[j][i]) res++;
            }
            if (res>=n-1){
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }
}


3.最短路径


给定一个 n 个点 m 条边构成的无重边和自环的无向连通图。


点的编号为 1∼n。


请问:


从 1 到 n 的最短距离。

去掉 k 条边后,从 1 到 n 的最短距离。

题目链接:最短路径 https://www.acwing.com/problem/content/description/3559/      


这是一道Floyd的练手模板题,不过题目存在一些要注意的问题,是多组测试数据所以每次我们都需要初始化一下数组,然后需要存一下需要删除的边,而且图是无向图。这里直接贴上模板代码。


import java.util.*;
public class Main {
    static int N=60;
    static int[][] g=new int[N][N];
    static int[][] bck=new int[N][N];
    static int n,m,k,INF=0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while (t-->0){
            n=sc.nextInt();
            m=sc.nextInt();
            k=sc.nextInt();
            init();
            List<int[]> list=new ArrayList<>();
            for (int i = 0; i < m; i++) {
                int a=sc.nextInt();
                int b=sc.nextInt();
                int w=sc.nextInt();
                g[a][b]=g[b][a]=w;
                bck[a][b]=bck[b][a]=w;
                list.add(new int[]{a,b});
            }
            System.out.println(floyd(g));
            for (int i = 0; i < k; i++) {
                int m=sc.nextInt();
                int[] curr=list.get(m-1);
                int a=curr[0];
                int b=curr[1];
                bck[a][b]=bck[b][a]=INF;
            }
            System.out.println(floyd(bck));
        }
    }
    static int floyd(int[][] f){
        for (int k = 1; k <=n; k++) {
            for (int i = 1; i <=n; i++) {
                for (int j = 1; j <=n; j++) {
                    f[i][j]= Math.min(f[i][j],f[i][k]+f[k][j]);
                }
            }
        }
        return f[1][n]==INF?-1:f[1][n];
    }
    static void init(){
        for (int i = 1; i <=n; i++) {
            Arrays.fill(g[i],INF);
            Arrays.fill(bck[i],INF);
            g[i][i]=bck[i][i]=0;
        }
    }
}


相关文章
|
12月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
632 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
算法
Floyd算法
Floyd算法
186 1
|
8月前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
8月前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
12月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
算法 定位技术
路径规划算法 - 求解最短路径 - A*(A-Star)算法
路径规划算法 - 求解最短路径 - A*(A-Star)算法
1448 1
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
自然语言处理 算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
198 0
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
|
10天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
12天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)

热门文章

最新文章