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);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录