Polaris6G's blog

Stay humble,stay hungry.

0%

算法基础03

Posted on Edited on Valine:
  • DFS
  • BFS
  • 树与图的存储
  • 树与图的深度优先遍历
  • 树与图的宽度优先遍历
  • 拓扑排序
  • 最短路
    • 朴素dijkstra算法
    • 堆优化版dijkstra算法
    • Bellman-Ford
    • spfa
    • Floyd
  • 最小生成树
    • 朴素版Prim
    • Kruskal
  • 二分图
    • 染色法
    • 匈牙利算法
算法 数据结构 空间 性质
DFS stack O(h) 不具有最短性
BFS queue O(2^h) 最短路(边权为1)

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Scanner;

public class DFS{
    static int N = 10;
    static int n;
    static boolean[] st = new boolean[N];
    static int[] path = new int[N];

    static void dfs(int k){
        if(k == n){
            for(int i = 0; i < n; i++)System.out.print(path[i] + " ");
            System.out.println();
            return;
        }
        for(int i = 1; i <= n; i++){
            if(!st[i]){
                path[k] = i;
                st[i] = true;
                dfs(k + 1);
                st[i] = false;
            }
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(0);
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.*;

public class BFS {
    static int N = 110;
    static int n, m;//图的长宽
    static int hh, tt;//队头队尾
    static int[][] g = new int[N][N];//存图
    static int[][] d = new int[N][N];//存距离
    static PII[] q = new PII[N * N];//队列存下标x,y

//    static PII[][] prev = new PII[N][N];//存路径

    static int bfs() {
        hh = 0;
        tt = -1;
        d[0][0] = 0;
        q[++tt] = new PII(0, 0);
        //向量数组
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (hh <= tt) {
            PII t = q[hh++];
            for (int i = 0; i < 4; i++) {
                int x = t.first + dx[i];
                int y = t.second + dy[i];

                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                    d[x][y] = d[t.first][t.second] + 1;
//                    prev[x][y] = t;
                    q[++tt] = new PII(x,y);
                }
            }
        }
//        int x = n - 1;
//        int y = m - 1;
//        while(x !=0 || y != 0){
//            System.out.print(x + " " + y);
//            System.out.println();
//            PII t = prev[x][y];
//            x = t.first;
//            y = t.second;
//        }
        return d[n-1][m-1];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < n; i++) {
            String[] st = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                g[i][j] = Integer.parseInt(st[j]);
                d[i][j] = -1;
            }
        }
        System.out.println(bfs());
    }
}

class PII {
    int first, second;
    PII(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

树和图的存储

树是特殊的图->无环连通图

无向图是一种特殊的有向图（建两条边）

有向图：

  • 邻接矩阵 g[a,b] n^2 ->稠密图
  • 邻接表 n个单链表（拉链法）->稀疏图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Main{
    static int N = 100010;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 1;
    static int[] q = new int[N];
    
    boolean[] st = new boolean[N];
    //存储
    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    //DFS
    void dfs(int u){
        st[u] = true;//标记
        for(int i = h[u]; i != 0; i = ne[i]){
            int j = e[i];
            if(!st[j])dfs(j);
        }
    }
    
    int bfs(){
        int tt = 0;
        int hh = 0;
        q[0] = 1;//存储起始点
        while(hh <= tt){
            int t = q[hh++];//出队
            for(int i = h[t]; i != 0; i = ne[i]){
                int j = e[i];
                if(!st[j]){
                    st[j] = true;
                    q[++tt] = j;
                }
            }
        }
        return ...;
    }
    
    public static void main(String[] args){
        dfs(i);
        bfs();
    }
}

拓扑序列

对于图A中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列

有向无环图->拓扑图

一个有向无环图一定至少存在一个入度为0的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class top_sort {//拓扑序列
    static int N = 100010;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] q = new int[N];
    static int[] d = new int[N];//存入度
    static int idx = 1, n;

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean topSort() {
        int tt = -1, hh = 0;
        for (int i = 1; i <= n; i++) {//让所有入度为0的节点入队
            if (d[i] == 0) q[++tt] = i;
        }
        while (hh <= tt) {
            int t = q[hh++];
            for (int i = h[t]; i != 0; i = ne[i]) {
                int j = e[i];
                if (--d[j] == 0) q[++tt] = j;//入队
            }
        }
        return tt == n - 1;//判断所有点是否都入队了->存在环则必有点入度始终不为0
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            d[b]++;//b入度+1
            add(a, b);
        }
        if (topSort()) {
            for (int i = 0; i < n; i++) System.out.print(q[i] + " ");
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }
}

最短路

  • 单源最短路->一个点到其他所有点的最短距离
    • 所有边权都是正数
      • 朴素Dijkstra算法 O(n^2) 适用于稠密图
      • 堆优化版Dijkstra算法 O(mlogn) 适用于稀疏图
    • 存在负权边
      • Bellman-Ford O(nm)
      • SPFA 一般O(m) 最坏O(nm)
  • 多源汇最短路->询问多个点到其他所有点的最短距离
    • Floyd算法 O(n^3)

朴素dijkstra算法

复杂度：

寻找路径最短的点：O(n^2)

更新距离：O(m)

所以总的时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.*;
import java.util.Arrays;

public class Main {
    static int N = 510;
    static int[][] g = new int[N][N];//稠密图使用邻接矩阵存储
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N]; //相当于s集合,确定了和1号店的最短距离的点加入到s集合中
    static int n;
    static int MAX  = 0x3f3f3f3f;

    static int Dijkstra() {
        Arrays.fill(dist, MAX);
        dist[1] = 0;
        for (int i = 1; i <= n; i++) {
            //找到当前距离1号点最近的点t
            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.min(dist[j], dist[t] + g[t][j]);
            }
        }
        if(dist[n]==MAX)return -1;
        return dist[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);

        //初始化g为正无穷,解决重边的问题
        for (int i = 1; i <= n; i++) Arrays.fill(g[i], MAX);

        while (m-- > 0) {
            String[] arr = br.readLine().split(" ");
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            int c = Integer.parseInt(arr[2]);
            g[a][b] = Math.min(g[a][b], c);
        }
        System.out.println(Dijkstra());
    }

}

堆优化版dijkstra算法

复杂度：

寻找路径最短的点：O(n) <- O(1)*n

加入集合S：O(n)

更新距离：O(mlogn) <- O(logn)*m

c++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010; // 把N改为150010就能ac

// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
    // 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x]; 
    h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
    while(heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

public class dijkstra_heap {
    static int N = 150010;
    static int n;

    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] w = new int[N];
    static int idx = 1;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int INF = 0x3f3f3f3f;

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static int dijkstra() {
        PriorityQueue<PII> queue = new PriorityQueue<>();
        Arrays.fill(dist, INF);
        dist[1] = 0;
        queue.add(new PII(0, 1));
        while (!queue.isEmpty()) {
            //1、找到当前未在s中出现过且离源点最近的点
            PII p = queue.poll();
            int distant = p.getDistant();
            int t = p.getIndex();
            if (st[t]) continue;
            //2、将该点进行标记
            st[t] = true;
            //3、用t更新其他点的距离
            for (int i = h[t]; i != 0; i = ne[i]) {
                int j = e[i];
                if (dist[j] > distant + w[i]) {
                    dist[j] = distant + w[i];
                    queue.add(new PII(dist[j], j));
                }
            }
        }
        if (dist[n] == INF) return -1;
        return dist[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a, b, c);
        }
        System.out.println(dijkstra());
    }

    static class PII implements Comparable<PII> {
        private final int index;
        private final int distant;

        public int getIndex() {
            return index;
        }

        public int getDistant() {
            return distant;
        }

        public PII(int distant, int index) {
            this.distant = distant;
            this.index = index;
        }

        @Override
        public int compareTo(PII o) {
            return Integer.compare(distant, o.distant);
        }

    }
}

Bellman-Ford

Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

(通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新)

bellman - ford算法擅长解决有边数限制的最短路问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class bellman_ford {
    static int N = 505;
    static int M = 10005;

    static class Edges {//结构体存边
        public int a;
        public int b;
        public int c;

        Edges(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    static int n, m, k;
    static Edges[] e = new Edges[M];

    static int[] dist = new int[M];
    static int[] backup = new int[M];//备份数组
    static int max = 0x3f3f3f3f;

    static void bellmanFord() {
        Arrays.fill(dist, max);//初始化一开始全部都是max
        dist[1] = 0;//初始化一开始全部都是max

        for (int i = 0; i < k; i++) {
            backup = Arrays.copyOf(dist, n + 1);
            for (int j = 0; j < m; j++) {
                int a = e[j].a;
                int b = e[j].b;
                int c = e[j].c;
                dist[b] = Math.min(dist[b], backup[a] + c);//用上面的点来更新后面的点
            }
        }
        //因为到不了最后的n点，然后存在负权边能够到达n，将n的值更新了之后，变得比max小，防止出现这种情况
        if (dist[n] > max / 2) System.out.println("impossible");
        else System.out.println(dist[n]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        k = Integer.parseInt(str[2]);
        for (int i = 0; i < m; i++) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            e[i] = new Edges(a, b, c);
        }
        bellmanFord();
    }

}

spfa

通过队列来优化bellman的步骤： dist[b] = Math.min(dist[b], dist[a] + c)

一定有dist[a]减小才有dist[b]的更新，故通过队列优化（与dijkstra类似）

队列中存储的都是自身更新后可能会引起其他点变化的点（只干有用的事，无用的点不存）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

//不存在负环
public class spfa {
    static int N = 100010;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] w = new int[N];
    static int idx = 1, n;
    static int MAX = 0x3f3f3f3f;

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void Spfa() {
        Queue<Integer> q = new LinkedList<>();
        Arrays.fill(dist, MAX);
        dist[1] = 0;
        st[1] = true;
        q.offer(1);
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            //遍历这个点连接的所有边
            for(int i = h[t]; i != 0; i = ne[i]){
                int j = e[i];
                //更新一下最短路
                if(dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    //当前点被更新，加入队列
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        if(dist[n] == MAX)System.out.println("impossible");
        else System.out.println(dist[n]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a, b, c);
        }
        Spfa();
    }
}

spfa判断负环：

维护每个节点的cnt[]数组，记录路径长度，如果cnt[j]>=n，根据抽屉原理，所谓最短路一定走过了n条边，即n+1个点，说明其中两个点相同，即存在负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

//不存在负环
public class Main {
    static int N = 100010;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] w = new int[N];
    static int[] cnt = new int[N];
    static int idx = 1, n;
    static int MAX = 0x3f3f3f3f;

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean Spfa() {
        Queue<Integer> q = new LinkedList<>();
        //全部点入队这样就没有负环无法经过,题中没说是否是连通图
        for(int i = 1; i <= n; i++){
            st[i] = true;
            q.offer(i);
        }
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            //遍历这个点连接的所有边
            for(int i = h[t]; i != 0; i = ne[i]){
                int j = e[i];
                //更新一下最短路
                if(dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    //记录路径长度
                    cnt[j] = cnt[t] + 1;
                    //如果长度大于等于n,说明走过n+1个点,说明走过负环
                    if(cnt[j] >= n)return true;
                    //当前点被更新，加入队列
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
       return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a, b, c);
        }
        if(Spfa())System.out.println("Yes");
        else System.out.println("No");
    }
}

Floyd算法

时间复杂度:O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class floyd {
    static int N = 210;

    static int n;
    static int[][] d = new int[N][N];
    static int INF = 0x3f3f3f3f;
    
	//精髓 dp[k,i,j]->在1~k个点中考虑i,j的最短路
    //递推式 dp[k,i,j] = dp[k-1,i,k] + dp[k-1,k,j];
    //化简:dp[i,j] = dp[i,k] + dp[k,j];
    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]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int k = Integer.parseInt(str[2]);

        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] = INF;
            }

        while(m-- != 0){
            String[] s1 = br.readLine().split(" ");
            int x = Integer.parseInt(s1[0]);
            int y = Integer.parseInt(s1[1]);
            int z = Integer.parseInt(s1[2]);
            d[x][y] = Math.min(d[x][y], z);//重边取最小
        }
        Floyd();

        while(k-- != 0){
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int t = d[a][b];
            if(t > INF/2)System.out.println("impossible");
            else System.out.println(t);
        }
    }
}

最小生成树

针对无向图

  • Prim
    • 朴素版Prim（稠密图）O(n^2)
    • 堆优化版的Prim（稀疏图）O(mlogn)
  • Kruskal （稀疏图）O(mlogm)

朴素版Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//朴素prim算法(稠密图)
public class prim {
    static int N = 510;
    //static int M = 100010;//m ~ n ^ 2 稠密图
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[][] g = new int[N][N];
    static int INF = 0x3f3f3f3f;
    static int n, m;

    static int Prim() {
        Arrays.fill(dist, INF);
        int res = 0;
        dist[1] = 0;
        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;
            }
            //说明图不连通,无最小生成树
            if (dist[t] == INF) return INF;
            //选出一条最小生成树的边,记录下来
            res += dist[t];
            st[t] = true;
            //更新其他点到集合的距离->已经在集合内的就不必再更新了防止捣乱
            for (int j = 1; j <= n; j++) {
                if (!st[j]) dist[j] = Math.min(dist[j], g[t][j]);
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        for (int i = 1; i <= n; i++) Arrays.fill(g[i], INF);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            g[a][b] = g[b][a] = Math.min(g[a][b], c);//无向图不要忘记
        }
        int t = Prim();
        if (t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
}

Kruskal

  • 将所有边按权重从小到大排序O(mlogm)

  • 枚举每条边a,b 权重c

    如果a,b不连通，将这条边加入集合中 O(m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010;
    static int M = 2 * N;
    static int[] p = new int[N];
    static int INF = 0x3f3f3f3f;
    static int n, m;

    static class edge implements Comparable<edge> {
        int a, b, w;

        edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }

        @Override
        public int compareTo(edge o) {
            return Integer.compare(this.w, o.w);
        }
    }

    static edge[] e = new edge[M];

    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static int Kruskal() {
        Arrays.sort(e, 0, m);//0~m-1排序
        for (int i = 1; i <= n; i++) p[i] = i;
        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)return INF;//不连通
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        for (int i = 0; i < m; i++) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int w = Integer.parseInt(s[2]);
            e[i] = new edge(a, b, w);
        }
        int t = Kruskal();
        if (t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
}

二分图

  • 染色法 O(n+m)
  • 匈牙利算法 最坏O(mn) 实际运行时间一般远小于O(mn)

二分图：图中点可以分到两个集合中，且边都是一个集合指向另一个集合，集合内部没有边

染色法

二分图<=>不含奇数环<=>二染色不矛盾

O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class colour {
    static int N = 100010;
    static int M = 2 * N;
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] h = new int[N];
    static int[] color = new int[N];
    static int idx = 1, n, m;

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean dfs(int u, int c) {
        color[u] = c;
        for (int i = h[u]; i != 0; i = ne[i]) {
            int j = e[i];
            if (color[j] == 0) {//未染色
                if (!dfs(j, 3 - c))return false;
            }
            else if(color[j] == c)return false;//矛盾
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            add(a, b);
            add(b, a);
        }
        boolean flag = true;
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0)
                if (!dfs(i, 1)) {
                    flag = false;
                    break;
                }
        }
        if (flag) System.out.println("Yes");
        else System.out.println("No");
    }
}

匈牙利算法

已知二分图，求两个点集中边数的最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class xiongyali {
    static int N = 505;
    static int M = 100010;
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] h = new int[N];
    static int[] match = new int[N];//match是表示女生对应的男生是谁
    static boolean[] st = new boolean[N];
    static int idx = 1, n1, n2;

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean find(int x) {
        //每一次遍历一遍传进来的左边集合x对应的右边集合中的点
        for (int i = h[x]; i != 0; i = ne[i]) {
            int j = e[i];
            // 判断这个点是不是已经用过了，没用过继续
            if (!st[j]) {
                st[j] = true;//递归判重防止死循环
                //女生还没被匹配或者谦让的美德起了作用
                if (match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n1 = Integer.parseInt(str[0]);
        n2 = Integer.parseInt(str[1]);
        int m = Integer.parseInt(str[2]);
        while (m-- != 0) {
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            add(a, b);
        }
        int res = 0;
        for (int i = 1; i <= n1; i++) {
            //每一次模拟都要将st数组清空,这个判断重复的点,match是物有所主了
            //st数组用来保证本次匹配过程中，右边集合中的每个点只被遍历一次，防止死循环
            //match存的是右边集合中的每个点当前匹配的点是哪个，但就算某个点当前已经匹配了某个点
            //也有可能被再次遍历，所以不能起到判重的作用
            Arrays.fill(st, false);
            if (find(i)) res++;
        }
        System.out.println(res);
    }
}