基础算法--搜索与图论（2）

最短路

n 表示点数量 m：边数量

稠密图：m和n^2是一个级别的

稀疏图：m和n一个级别

• **单源最短路：**一个点到其他点的最短距离

  • 所有边权重都是正数：朴素Dijkstra算法 n^2，堆优化版Dijkstra算法 mlogn

    所以朴素的适合稠密图

  • 存在负权边：Bellman-Ford算法 nm ，SPFA 算法 一般是m，最坏nm

• **多源汇最短路：**起点和终点都是不确定的

  • Foyld算法： n^3

单源最短路

dijkstra算法（朴素）

1. 初始化距离：设一号点 dis[1] = 0 即到起点的距离为0，其他都为正无穷，dis[ i ] = +∞
2. 循环n次，每次循环
   找到不在s（保存当前已经确定最短路径的点的集合）中的，距离最近的点t（这个t的现在的距离一定是最短路，具体可以证明），再将t加入集合s中，
   用t更新其他点的最短距离 查看dis[x] > dis[t] + t到x边的权重是否成立，是，就将x距离更新

每次循环就能确定一个点的最短路

模板：

public class Main{static final int N = 510;static int[]dist = new int[N];//每个点到起点的最短路static boolean[]st = new boolean[N];//这个点是否已经确定最短路static int[][]g = new int[N][N];//邻接矩阵存储稠密图static int MAX = 0x3f3f3f3f;static int n;//有几个点static int m;//有几个边static int dijkstra() {Arrays.fill(dist,MAX);dist[1] = 0;//初始化距离for(int i = 0;i < n;i++) {//找到一个距离起点最近且没确定最短路的点tint t = -1;for(int j = 1;j <= n;j++) {if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;}//这个t此时与起点的距离就是该点的最短路st[t] = true;//用这个t更新其他点的距离for(int j = 1;j <= n;j++) {dist[j] = Math.min(dist[j],dist[t] + g[t][j]);//这里如果t和j无关联，那么g[t][j]就是MAX，dist[j]仍然是MAX}}//dist[n]是MAX说明n点与起点不存在路径if(dist[n] == MAX) return -1;return dist[n];}public static void main(String[]args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {if(i == j) g[i][j] = 0;//自环边else g[i][j] = MAX;}}while(m --> 0 ) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();g[a][b] = Math.min(g[a][b],c);//a和b之间可能有多条路，取最短的一条}System.out.println(dijkstra());}
}

dijkstra算法（堆优化）

复杂度为mlogn

使用最小堆来优化找到一个距离起点最近且没确定最短路的点t过程

import java.util.*;public class Main{static final int N = 150010;static int[]e = new int[N];static int[]h = new int[N];//使用邻接表来存稀疏图static int[]w = new int[N];static int[]ne = new int[N];static int[]dist = new int[N];static int M = 0x3f3f3f3f;static int idx;static int n;static int m;static PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);static boolean[]st = new boolean[N];static int dijkstra() {Arrays.fill(dist,M);dist[1] = 0;heap.offer(new int[]{1,0});/** 不优化的算法是采取暴力的方式，每次都把所有点遍历一遍，找st[j]=false且离起点最近的* 这里借助堆，每次将t更新完的其他点放入堆中，从堆中取出时，再用取出的点更新其他点，再次放入堆中*/while(heap.size() != 0) {int[]a = heap.poll();int t = a[0];int distan = a[1];st[t] = true;for(int i = h[t];i != -1;i = ne[i]) {int j = e[i];if(dist[j] > distan + w[i]) {dist[j] = distan + w[i];heap.offer(new int[]{j,dist[j]});}}}if(dist[n] == M) return -1;return dist[n];}static void add(int a,int b,int c) {e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;}public static void main(String[]args) {Arrays.fill(h,-1);Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();while(m --> 0) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();add(a,b,c);}System.out.println(dijkstra());}
}

存在负权边

Bellman-Ford算法

有边数限制的话，只能用它

图中不能存在负权回路，否则在回路中一直转圈，最短路就变成负无穷即不存在最短路

循环n次（表示最多不经过n条边）将dist复制给c，下边的循环用c中的数据更新dist（防止连路）循环所有边（a，b，w）dis[b] = min(dist[b],copy[a] + w);//松弛操作

这样循环n次后，对于所有的点都满足三角不等式dist[b] <= dist[a] + w ，可以证明

直接用一个数组存放所有的边

public static int bellmanFord() {Arrays.fill(dist,M);dist[1] = 0;for(int i = 0;i < k;i++) {int[] c = Arrays.copyOf(dist, N);for(int j = 1;j <= m;j++) {int a = e[j].a;int b = e[j].b;int w = e[j].w;dist[b] = Math.min(dist[b],c[a] + w);}}if(dist[n] > M / 2) return M;return dist[n];
}

SPFA

实际上是对Bellman-ford算法的优化，主要思路是记录哪些点被更新了，再将和这些点有关系的点更新

迭代时用一个队列存放刚被更新的点（先将起点放入队列）

只要队列不空

​ 将对头t取出

​ 遍历更新一下t的所有出边b

​ 将b加入队列（b在队列中不存在的话）

public class Main{static final int N = 100010;static int n;static int m;static int[]h = new int[N];static int[]w = new int[N];static int[]ne = new int[N];static int[]e = new int[N];static boolean[]st = new boolean[N];static int idx;static int[]dist = new int[N];static int M = 0x3f3f3f3f;static void add(int x,int y,int z) {e[idx] = y;ne[idx] = h[x];w[idx] = z;h[x] = idx++;}public static void main(String[]args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();Arrays.fill(h,-1);while(m --> 0) {int x = sc.nextInt();int y = sc.nextInt();int z = sc.nextInt();add(x,y,z);}int t = spfa();if(t == M) System.out.println("impossible");else System.out.println(t);}public static int spfa() {Arrays.fill(dist,M);dist[1] = 0;Queue<Integer> queue = new LinkedList<>();queue.offer(1);st[1] = true;while(!queue.isEmpty()) {int t = queue.poll();st[t] = false;for(int i = h[t];i != -1;i = ne[i]) {int j = e[i];if(dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];if(!st[j]) {queue.offer(j);st[j] = true;}}}}if(dist[n] == M) return M;return dist[n];}}

多源汇求最短路

Flyod

初始时用邻接矩阵存储边d[i,j]

for(k = 1;k <= n;k++)for(i = 1;i <= n;i++)for(j = 1;j <= n;j++)d[i,j] = min(d[i,j],d[i,k]+d[k,j]);

模版：

import java.util.Scanner;public class Main{static final int N = 210;static int[][]d = new int[N][N];static int M = 0x3f3f3f3f;static int n;static int m;public static void main(String[]args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();int k = sc.nextInt();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {if(i == j) d[i][j] = 0;else d[i][j] = M;}}while(m --> 0) {int x = sc.nextInt();int y = sc.nextInt();int z = sc.nextInt();d[x][y] = Math.min(d[x][y],z);}floyd();while(k --> 0) {int x = sc.nextInt();int y = sc.nextInt();if(d[x][y] > M / 2) System.out.println("impossible");else System.out.println(d[x][y]);}}static void floyd() {for(int k = 1;k <= n;k++) {for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {d[i][j] = Math.min(d[i][j],d[i][k] + d[k][j]);}}}}
}

最小生成树

最小生成树问题一般对应无向图

一般稠密图用朴素版的Prim算法，稀疏图用Kruskal算法

• Prim算法
  • 朴素版（稠密图）On^2
  • 堆优化版（稀疏图）Omlogn
• Kruskal算法 Omlogm

Prim（朴素版）

集合：指当前已经在连通块中的点

到集合的距离：指到集合中的最近的点的距离

1. 把所有距离初始化成正无穷
2. n次迭代，每次迭代时，找到不在集合中的距离最近的点t，把t加到集合中（st[ t ] = true），用t来更新其他点到集合的距离

public class Main{static final int N = 510;static int[][]g = new int[N][N];static boolean[]st = new boolean[N];static int[]dist = new int[N];static int M = 0x3f3f3f3f;static int n;static int m;static int prim() {Arrays.fill(dist,M);int res = 0;//记录最小生成树的权重之和for(int i = 0;i < n;i++) {int t = -1;for(int j = 1;j <= n;j++) {if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;}st[t] = true;if(i != 0 && dist[t] == M) return M;//距离集合最近的点到集合的距离还是M，说明这个点和集合不连通，不存在最小生成树if(i != 0) res += dist[t];//这里将找到的一个结果加进结果集需要在根据t更新其他点到集合的距离之前，为了防止自环边的影响for(int j = 1;j <= n;j++) dist[j] = Math.min(dist[j],g[t][j]);}return res;}public static void main(String[]args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {g[i][j] = M;}}while(m --> 0) {int x = sc.nextInt();int y = sc.nextInt();int z = sc.nextInt();g[x][y] = g[y][x] = Math.min(g[x][y],z);}int r = prim();if(r == M) System.out.println("impossible");else System.out.println(r);}
}

Krusal算法

1. 将所有边按权重从小到大排序（该算法的一个瓶颈）
2. 枚举每条边ab和权重c，如果a，b不连通（不在同一个集合中），将这条边加入集合 // 使用并查集

import java.util.*;
class Edge implements Comparable{int a;int b;int w;public Edge(int a,int b,int w) {this.a = a;this.b = b;this.w = w;}@Overridepublic int compareTo(Object o) {Edge e = (Edge)o;return this.w - e.w;}
}public class Main {static final int N = 100010;static int[]p = new int[N];static int find(int x) {if(x != p[x]) p[x] = find(p[x]);return p[x];}public static void main(String[]args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for(int i = 1;i <= n;i++) p[i] = i;int m = sc.nextInt();Edge[]e = new Edge[m];for(int i = 0;i < m;i++) {int u = sc.nextInt();int v = sc.nextInt();int w = sc.nextInt();e[i] = new Edge(u,v,w);}Arrays.sort(e);//将所有边按权重从小到大排序int res = 0;int cnt = 0;for(int i = 0;i < m;i++) {//如果两点之间根本不连通（没有边），那么根本不会枚举不存在的边int a = e[i].a;int b = e[i].b;int w = e[i].w;a = find(a);b = find(b);if(a != b) {//若两者根父节点不同，则两点不在同一个集合中p[a] = b;//并查集合并集合res += w;cnt++;}}if(cnt < n - 1) System.out.println("impossible");else System.out.println(res);}
}

二分图

一个图是二分图当且仅当图中不含奇数环。

二分图：图中所有点都可以分成两部分，每一部分之间没有边相连。

• 如何判别一个图是不是二分图：染色法 On+m
• 匈牙利算法 Onm，实际运行时间一般远小于nm

染色法

保证一条边的两个端点属于不同的集合，总共两个集合（即两种颜色）

for(int i = 1;i <= n;i++) {if (i 未染色) dfs(i,k)  // 将i点颜色定为k，用深度优先遍历将i相连的点的颜色全部确定
}

import java.util.*;public class Main{static int n;static int m;static final int N = 100010;static final int M = 200010;static int[]h = new int[N];static int[]e = new int[M];static int[]ne = new int[M];static int idx;static int[]col = new int[N];static void add(int a,int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}static boolean dfs(int k,int color) {col[k] = color;for(int i = h[k];i != -1;i = ne[i]) {int j = e[i];if(col[j] == 0) {if(!dfs(j,3 - color)) return false;}else if(col[j] == color) return false;}return true;}public static void main(String[]args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();Arrays.fill(h,-1);while(m --> 0) {int u = sc.nextInt();int v = sc.nextInt();add(u,v);add(v,u);}for(int i = 1;i <= n;i++) {if(col[i] == 0) {if(!dfs(i,1)) {System.out.println("No");return;}}}System.out.println("Yes");}
}

练习：acwing 关押罪犯

匈牙利算法

没有两条边共用一个点称为成功匹配

匈牙利算法可以返回成功匹配最大的情况

public class Main{static final int N = 1010;static final int M = 100010;static int[]h = new int[N];static int[]e = new int[M];static int[]ne = new int[M];static int idx;static int n1;static int n2;static int m;static boolean[]st = new boolean[N];static int[]match = new int[N];//每个索引代表一个女嘉宾，索引下的值代表对应男嘉宾static void add(int a,int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}public static void main(String[]args) {Scanner sc = new Scanner(System.in);n1 = sc.nextInt();n2 = sc.nextInt();m = sc.nextInt();Arrays.fill(h,-1);while(m --> 0) {int u = sc.nextInt();int v = sc.nextInt();add(u,v);}int res = 0;for(int i = 1;i <= n1;i++) {Arrays.fill(st,false);if(find(i)) res++;}System.out.println(res);}static boolean find(int x) {for(int i = h[x];i != -1;i = ne[i]) {int j = e[i];if(!st[j]) {st[j] = true;//这里将他设置为true是为了在下面劝拥有这个妹子的男生找其他的妹子时不要重复找了这个妹子if(match[j] == 0 || find(match[j])) {//妹子待字闺中 或 成功分手match[j] = x;//将这个妹子匹配给这个男生 牵手成功return true; }}}return false;}
}