概述
Floyd算法及其变形
例题：牛的旅行
【题目描述】
农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径 ( 注意，恰好一条 )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都是最短的距离 )。考虑如下的两个牧场，图１是有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：
图１所示的牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。
这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。
【输入】
第 1 行：一个整数N (1 ≤ N ≤ 150), 表示牧区数；
第 2 到 N+1 行：每行两个整数X，Y ( 0 ≤ X，Y≤ 100000 )， 表示N个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2*N+1 行：每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵。
例如，题目描述中的两个牧场的矩阵描述如下：
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
输入数据中至少包括两个不连通的牧区。
【输出】
只有一行，包括一个实数，表示所求答案。数字保留六位小数。
【输入样例】
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
【输出样例】
22.071068
————————————————————————————————————————————————————
import java.util.*;
public class Main {
static double INF = 1e20;
static int N = 150;
static int n;
static Pair[] q = new Pair[N];
static double[][] d = new double[N][N];
static double[] maxd = new double[N];
static char[][] g = new char[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
q[i] = new Pair(x, y);
}
for (int i = 0; i < n; i++) {
g[i] = sc.next().toCharArray();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
if (g[i][j] == '1') {
d[i][j] = get_dist(q[i], q[j]);
}else {
d[i][j] = INF;
}
}
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d[i][j] < INF) {
maxd[i] = Math.max(maxd[i], d[i][j]);
}
}
}
double res1 = 0;
for (int i = 0; i < n; i++) {
res1 = Math.max(res1, maxd[i]);
}
double res2 = INF;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d[i][j] >= INF) {
res2 = Math.min(res2, get_dist(q[i], q[j]) + maxd[i] + maxd[j]);
}
}
}
System.out.printf("%.6f", Math.max(res1, res2));
}
private static double get_dist(Pair a, Pair b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return Math.sqrt(dx * dx + dy * dy);
}
}
class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
例题：343. 排序
floyd解决传递闭包问题，核心思想:i --> k且k --> j，则i – > j
情况1、矛盾，d[i,i] = 1;
情况2、唯一确定，对于所有i != j,且d[i,j]和d[j,i]有且只有一个均成立
情况3、顺序不唯一
当所有的关系大小均确定的时候，需要从小到大输出字母编号，调用 getSequence() 输出，由于已经传递闭包过，因此所有的关系已经确定，对于闭包后的每一对关系，假设A > B,因此 A 的等级就加 1，遍历所有传递闭包后的关系，对相应的等级进行累加，再对等级大小进行排序，等级越大的字母大小关系也越大
注意：题目说到从前往后遍历每对关系，每次遍历时判断，因此每一次新增一关系都得做 floyd 和 check() 判断
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 26;
static int[][] g = new int[N][N];
static int[][] dist = new int[N][N];
static int n, m;
static Pair[] level = new Pair[N];
static void floyd() {
dist = g.clone();
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (dist[i][k] == 1 && dist[k][j] == 1) {
dist[i][j] = 1;
}
}
}
static int check() {
for (int i = 0; i < n; i++) if (dist[i][i] == 1) return 2;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) {
if ((dist[i][j] == 0 && dist[j][i] == 0)) return 0;
}
return 1;
}
static String getSequence() {
for (int i = 0; i < n; i++) level[i] = new Pair((char) ('A' + i), 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) {
//dist[i][j]不为1，对称的一边一定为1
if (dist[i][j] == 1) level[j].d++;
else level[i].d++;
}
Arrays.sort(level, 0, n);
String res = "";
for (int i = 0; i < n; i++) {
res += level[i].c;
}
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (true) {
n = scan.nextInt();
m = scan.nextInt();
if (n == 0 && m == 0) break;
for (int i = 0; i < n; i++) Arrays.fill(g[i], 0);
int type = 0, t = 0; // type - 0：不确定，1：唯一确定，2：矛盾
while (m-- > 0) {
char[] charArray = scan.next().toCharArray();
if (type > 0) continue;
int a = charArray[0] - 'A', b = charArray[2] - 'A';
g[a][b] = 1;//表示a < b
floyd();
type = check();
t++;
}
if (type == 0) {
System.out.println("Sorted sequence cannot be determined.");
}else if (type == 2) {
System.out.println("Inconsistency found after " + t + " relations.");
}else {
System.out.println("Sorted sequence determined after " + t + " relations: " + getSequence() + ".");
}
}
}
}
class Pair implements Comparable<Pair> {
char c;//当前字符
int d;
Pair(char c, int d) {
this.c = c;
this.d = d;
}
@Override
public int compareTo(Pair o) {
return Integer.compare(d, o.d);
}
}
例题：344. 观光之旅
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int INF = Integer.MAX_VALUE >> 1;
static int N = 110;
static int n;
static int m;
static int[][] d = new int[N][N];
static int[][] g = new int[N][N];
static int[][] pos = new int[N][N];
static int[] path = new int[N];
static int cnt;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int[] x : g) Arrays.fill(x, INF);
for (int i = 1; i <= n; i++) {
g[i][i] = 0;
}
while (m-- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
g[a][b] = Math.min(g[a][b], c);
g[b][a] = g[a][b];
}
int res = INF;
for (int i = 0; i < d.length; i++) {
d[i] = g[i].clone();
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++) {
for (int j = i + 1; j < k; j++) {
if ((long)d[i][j] + g[j][k] + g[k][i] < res) {
res = d[i][j] + g[j][k] + g[k][i];
cnt = 0;
path[cnt++] = k;
path[cnt++] = i;
get_path(i, j);
path[cnt++] = j;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
pos[i][j] = k;
}
}
}
}
if (res == INF) {
System.out.printf("No solution.");
} else {
for (int i = 0; i < cnt; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
}
}
private static void get_path(int i, int j) {
if (pos[i][j] == 0) return;
int k = pos[i][j];
get_path(i, k);
path[cnt++] = k;
get_path(k, j);
}
}
例题：345. 牛站
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static int INF = Integer.MAX_VALUE >> 1;
static int N = 210;
static int k;
static int n;
static int m;
static int S;
static int E;
static int[][] g = new int[N][N];
static int[][] res= new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
k = sc.nextInt();
m = sc.nextInt();
S = sc.nextInt();
E = sc.nextInt();
for (int[] x : g) Arrays.fill(x, INF);
// for (int i = 1; i < N; i++) {
// g[i][i] = 0;
// }
Map<Integer, Integer> ids = new HashMap<>();
if (!ids.containsKey(S)) ids.put(S, ++n);
if (!ids.containsKey(E)) ids.put(E, ++n);
S = ids.get(S);
E = ids.get(E);
while (m-- > 0) {
int c = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
if (!ids.containsKey(a)) {
ids.put(a, ++n);
}
if (!ids.containsKey(b)) {
ids.put(b, ++n);
}
a = ids.get(a);
b = ids.get(b);
g[a][b] = Math.min(g[a][b], c);
g[b][a] = g[a][b];
}
qmi();
System.out.println(res[S][E]);
}
private static void qmi() {
for (int[] x : res) Arrays.fill(x, INF);
for (int i = 1; i <= n; i++) {
res[i][i] = 0;
}
while (k > 0) {
if ((k & 1) == 1) mul(res, res, g);
mul(g, g, g);
k >>= 1;
}
}
private static void mul(int[][] c, int[][] a, int[][] b) {
int[][] tmp = new int[N][N];
for (int[] x : tmp) Arrays.fill(x, INF);
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
tmp[i][j] = Math.min(tmp[i][j], a[i][k] + b[k][j]);
}
}
}
for (int i = 0; i < tmp.length; i++) {
c[i] = tmp[i].clone();
}
}
}
最后
以上就是专注荷花为你收集整理的第三章图论（四）的全部内容，希望文章能够帮你解决第三章图论（四）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![信息学奥赛一本通 1343：【例4-2】牛的旅行 | 洛谷 P1522 [USACO2.4] 牛的旅行 Cow Tours](/uploads/reation/bcimg13.png)
发表评论 取消回复