floyd 算法

floyd展开目录

floyd 算法解决的问题是在图中找到从 i 号结点到 j 号结点最短路径值（边的权值）的问题，核心代码就下面四行

for(int k = 0;k < n;k++)
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j]);

很容易理解，假设 i 和 j 中间有一个点 k，那么 i 到 j 的最短路径值肯定是 i 到 j，或者 i 先到 k 然后 k 到 j 两者中最小的

题目链接：Codeforces522A展开目录

题目大意是说，有一条消息，B 从 A 那里转发，C 从 B 那里转发，....，问最长的转发链长度是多少，你可以理解为 dfs 问题，也可以认为是 floyd 问题，如果用 floyd 解法来做就是算出每一个从 i 到 j 的最短路径值，然后再在其中找最大，注意人名统一大小写即可

import java.util.Scanner;
import java.util.TreeMap;
public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int num = 0;
        TreeMap<String,Integer> map = new TreeMap<>();
        int[][] dp = new int[250][250];
        
        for(int i = 0;i < 250;i++)
            for(int j = 0;j < 250;j++)
                dp[i][j] = 0x3f3f3f3f;
        
        for(int i = 0;i < n;i++) {
            String name1 = cin.next();
            name1 = name1.toLowerCase();
            cin.next();
            String name2 = cin.next();
            name2 = name2.toLowerCase();
            if(!map.containsKey(name1))
                map.put(name1,++num);
            if(!map.containsKey(name2))
                map.put(name2,++num);
            dp[map.get(name1)][map.get(name2)] = 1;
        }
        for(int k = 1;k <= num;k++) 
            for(int i = 1;i <= num;i++) 
                for(int j = 1;j <= num;j++) 
                    dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j]);
        
        int res = -0x3f3f3f3f;
        for(int i = 1;i <= num;i++) 
            for(int j = 1;j <= num;j++) 
                res = (dp[i][j] < 0x3f3f3f3f) ? Math.max(res,dp[i][j]) : res;
        System.out.println(res + 1);
    }
}

题目链接：CodeForces505B展开目录

这道题大意是说给一个 n 个点，m 条边的无向图，首先设置点 a 到 b 之间的边的颜色 c，然后有 q 次询问，问 u 到 v 有几种方法。假设 1 和 3 是不相连的，但是 2 分别连接 1 和 3，要想从 1 通过 2 走到 3，必须满足 1,2 之间边的颜色和 2,3 之间边的颜色相同

水题，类 floyd 算法，三维数组 dpc [j] 的值为 1 表示 i 到 j 有颜色为 c 的边，如果 dpc [j] 的值为 0，表示 i 到 j 没有颜色为 c 的边

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        int maxc = -1;
        int[][][] dp = new int[101][101][101];
        for(int i = 0;i < m;i++) {
            int a,b,c;
            a = cin.nextInt();
            b = cin.nextInt();
            c = cin.nextInt();
            maxc = Math.max(c,maxc);
            dp[c][a][b] = dp[c][b][a] = 1;
        }
        
        //floyd
        for(int c = 1;c <= maxc;c++) //颜色
            for(int k = 1;k <= n;k++) //中间点
                for(int i = 1;i <= n;i++) //起始点
                    for(int j = 1;j <= n;j++) //终止点
                        //i和j之间没有颜色为c的连线 && i到k之间有颜色为c的连线 && k到j之间有颜色为c的连线
                        if(dp[c][i][j] == 0 && dp[c][i][k] != 0 && dp[c][k][j] != 0)
                            //则i到j之间就有颜色为c的连线
                            dp[c][i][j] = dp[c][i][j] = 1;
        
        int q = cin.nextInt();
        while((q--) != 0) {
            int u = cin.nextInt();
            int v = cin.nextInt();
            int ans = 0;
            for(int i = 1;i <= maxc;i++)
                ans += dp[i][u][v];
            System.out.println(ans);
        }
    }
}

题目连接：CodeForces601A展开目录

题目大意是说，有 n 个城镇，两两之间必有路相连，不是铁路就是公路（只能有一种路），现在汽车和火车同时从 1 出发，问最晚达到 n 的用时是多长。很简单，如果铁路直接将 1 和 n 相连，就去对公路进行 floyd，反之就对铁路进行 floyd

import java.util.Scanner;
public class Main {
    public static int floyd(int[][] tmp,int n) {
        for(int k = 1;k <= n;k++) {
            for(int i = 1;i <= n;i++) {
                for(int j = 1;j <= n;j++) {
                    //中间点和起点或者终点都不可连 
                    if(tmp[i][k] == 0 || tmp[k][j] == 0) 
                        continue;
                    //如果起点和终点不可连，那么一定更新 
                    if(tmp[i][j] == 0) 
                        tmp[i][j] = tmp[i][k] + tmp[k][j];
                    tmp[i][j] = Math.min(tmp[i][j],tmp[i][k] + tmp[k][j]); 
                }
            }
        }
        return tmp[1][n];
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        int res;
        int[][] huo = new int[n + 1][n + 1];
        int[][] qi = new int[n + 1][n + 1];
        for(int i = 0;i < m;i++) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            huo[a][b] = huo[b][a] = 1;
        }
        
        if(huo[1][n] == 1) {//火车从1直达n
            for(int i = 1;i <= n;i++) 
                for(int j = 1;j <= n;j++)
                        qi[i][j] = 1 - huo[i][j];
            //汽车floyd
            res = floyd(qi,n);
        } else //汽车1直达n
            //火车floyd
            res = floyd(huo,n);
        
        if(res == 0)
            System.out.println(-1);
        else
            System.out.println(res);
    }
}