1. 题意
在一个既有有向边又有无向边的图中,每个点具有一个权值,问从1号点走到N号点的路径中,求经过权值最大点和权值最小点的最大差值。
2. 思路
dp + 最短路
dp的思想用集合的角度不重不漏的划分所有方案。
由于求max、min而不是求count所以可以重复。
枚举分界点k,求
1 ~ k之间权重的最小值dmin
k ~ n之间权重的最大值dmax
dmax - dmin 就是以k为分界点的答案,然后再枚举所有分界点取一个最大值即可。
3.为什么用到dp呢
y总讲的前缀知识:
dp的状态存在状态之间的依赖关系,则可以转化成最短路问题来做。
状态的依赖关系有点悬,先不管。
注意: DP只能处理拓扑图,由于此题不是拓扑图状态的更新可能存在环,所以不能使用动态规划。
4. 为什么不能用dijkstra,要用spfa
使用dijkstra要求当前最小值(堆顶)一定是最终最小值。
而此题因为不是拓扑图,可能存在环,刚开始拓展到2号点时,dmin[2] = 3,
随后经过4号点出边会更新掉dmin[2] = 1,所以当前最小值并不一定是最终最小值。
此题可以用spfa,spfa一般都是正确的,所以无脑用spfa就行。
5. 为啥要建反向图。
在计算dmin和dmax时需要从前面的那些点中获取信息。
计算1~k的dmin,需要获取1~k-1的所有信息,那么只需要正向遍历即可获取1~k-1的所有信息。
计算k~n的dmax,需要获取k~n的所有信息,而如果继续正向遍历的话,得到的是1~k-1的信息,所以需要建立反向图,由n号点作为起点,反向遍历,得到n~k+1的所有信息。
6. 代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N = 100010, M = 500010, INF = 0x3f3f3f3f;
static int[] hs = new int[N], he = new int[N], w = new int[M], e = new int[M], ne = new int[M];
static int[] dmin = new int[N], dmax = new int[N];
static int n, m, idx = 0;
static boolean[] st = new boolean[N];
static int[] q = new int[N];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for (int i = 1; i <= n; i ++ ) {
w[i] = Integer.parseInt(s2[i - 1]);
}
Arrays.fill(hs, -1);
Arrays.fill(he, -1);
while (m -- > 0) {
String[] s3 = br.readLine().split(" ");
int a = Integer.parseInt(s3[0]);
int b = Integer.parseInt(s3[1]);
int c = Integer.parseInt(s3[2]);
add(hs, a, b);
add(he, b, a);
if (c == 2) {
add(hs, b, a);
add(he, a, b);
}
}
//算最大值
spfa(hs, 0);
spfa(he, 1);
int res = 0;
for (int i = 1; i <= n; i ++ ) {
res = Math.max(res, dmax[i] - dmin[i]);
}
System.out.println(res);
}
public static void spfa (int[] h, int type) {
//更新st数组 fuck
Arrays.fill(st, false);
int hh = 0, tt = 1;
if (type == 0) {
Arrays.fill(dmin, INF);
dmin[1] = w[1];//正向图1是起点
q[0] = 1;
}
else {
Arrays.fill(dmax, -INF);
dmax[n] = w[n];//反向图n是起点
q[0] = n;
}
while (hh != tt) {
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;//st记录是否在队列中
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (type == 0 && dmin[j] > Math.min(dmin[t], w[j]) || type == 1 && dmax[j] < Math.max(dmax[t], w[j])) {
if (type == 0) dmin[j] = Math.min(dmin[t], w[j]);
else dmax[j] = Math.max(dmax[t], w[j]);
if (!st[j]) {
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
public static void add(int[] h, int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
}