算法分析
题目的问题:给定两个联通块,在两个连通块中各取任意一点进行连接合成一个连通块,求合并后的联通块的最长路径的最小值
-
1、各求出两个连通块内部的最长路径的最大值
res1
-
2、任意连接
i
点和j
点,合并成一个连通块,求合并后连通块的且经过i
点和j
点的最长路径的最小值res2 = min(maxd[i] + get(i,j) + maxd[j])
-
3、最终合并后连通块的最长路径(直径)的最小值为
ans = max(res1,res2)
;
详细步骤
-
1、用
floyd
算法求出任意两点之间的最短距离 -
2、求
maxd[i]
,表示和i
连通的且距离i
最远的点的距离 -
3、
-
(1)求所有
maxd[i]
的最大值res1
-
(2)枚举任意两点
i
,j
连边,满足d[i][j] > INF/2
,时 求res2 = min(maxd[i] + get(i,j) + maxd[j])
-
时间复杂度 $(n^3)$
参考文献
算法提高课
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static double INF = 0x3f3f3f3f;
static int N = 160;
static int n;
static Pair[] g = new Pair[N];
static double[][] dist = new double[N][N];
static double[] maxd = new double[N];
static double get_dist(int i,int j)
{
int x1 = g[i].x, x2 = g[j].x , y1 = g[i].y , y2 = g[j].y;
return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
static void floyd()
{
for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
int x = scan.nextInt();
int y = scan.nextInt();
g[i] = new Pair(x,y);
}
for(int i = 1;i <= n;i ++)
{
char[] charArray = scan.next().toCharArray();
for(int j = 1;j <= n;j ++)
{
if(i != j)
{
if(charArray[j - 1] == '1') dist[i][j] = get_dist(i,j);
else dist[i][j] = INF;
}
}
}
floyd();
double res1 = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
{
if(dist[i][j] < INF / 2)
{
maxd[i] = Math.max(maxd[i], dist[i][j]);
res1 = Math.max(res1, maxd[i]);
}
}
double res2 = INF;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
{
if(dist[i][j] > INF / 2)
{
res2 = Math.min(res2, maxd[i] + get_dist(i,j) + maxd[j]);
}
}
System.out.printf("%.6f",Math.max(res1, res2));
}
}
class Pair
{
int x;
int y;
Pair(int x,int y)
{
this.x = x;
this.y = y;
}
}
res1为什么要参与运算。没有加边算它有什么意义吗?
因为可能两个连通块内部的最长路径
res1
是才是最长的嗯,对的,后来我想明白了。👍