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);
    }
}