算法分析
A 最少需要多少钱使得转账后 B 收到 100 元
B = A * W1 * W2 * … Wn
要让 A的值最小 则 (W1 * W2 * … Wn) 最大
下面是选用朴素版的Dijkstra
算法,$n = 2000,n^2 = 4 * 10^6$
-
1、找到当前未标记过且值最大的点
-
2、标识该点
-
3、用该点更新其他点的值
时间复杂度 $O(n^2)$
参考文献
算法提高课
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
static int N = 2010;
static int n;
static int m;
static int INF = 0x3f3f3f3f;
static double[] dist = new double[N];
static boolean[] st = new boolean[N];
static double[][] g = new double[N][N];
static void dijkstra(int start)
{
dist[start] = 1;
for(int i = 0;i < n;i ++)
{
int t = -1;
for(int j = 1;j <= n;j ++)
{
if(!st[j] && (t == -1 || dist[t] < dist[j]))//往大的取
t = j;
}
st[t] = true;
for(int j = 1;j <= n;j ++)
{
dist[j] = Math.max(dist[j], dist[t] * g[t][j]);//往大的取
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
while(m -- > 0)
{
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
g[a][b] = g[b][a] = Math.max(g[a][b], (100.0 - c)/100);//往大的取
}
String[] s3 = br.readLine().split(" ");
int start = Integer.parseInt(s3[0]);
int end = Integer.parseInt(s3[1]);
dijkstra(start);
System.out.printf("%.8f", 100 / dist[end]);
}
}
y总的视频里怎么由对数相加推出来dist[j] <-dist[t] * g[t][j]是对的,对数的求w1w2.....wk的最大值,可以转化为对数即lg(w1w2.....wk)=lgw1+lgw2+....+lgwk的最大值,又有lgwi均<=0,所以令lgwi’=-lgwi,则为求lgw1’+lgw2’+…+lgwn’的最小值,代码里用的是wi来计算的,想问一下怎么推算过来的。
没看懂你想问什么..问哪里是推算过来的?
抱歉,我的意思是想问,y总推出来的是(-lgw1)+(-lgw2)+…+(-lgwn)这个是最短路径,为啥求最大w1w2w3....wn可以用上面的结论,他推出来的是对数取负数的最大值满足最小路径,但是代码里面写的用的是w1w2....wn的形式,并没有用对数的形式,感谢
他用lg只是想表达的是乘积最大可以 等价成 和最小的问题,求出lgw1’+lgw2’+…+lgwn’的最小值,就可以求出lg(w1w2.....wk)的最大值,等价于求w1w2.....wk的最大值,因此使用乘积最大 也可以 适用于 最短路问题,y总想表达的是这个,因此这里
dist[j] = Math.max(dist[j], dist[t] * g[t][j]);
才可以这么写,因为它可以等价成求加法的最小值感谢
没事hh