Post

搜索与图论

Posted Updated
By skye-ye

views 44 min read
搜索与图论

DFS 深度优先算法

排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：

1

3

输出样例：

1
2
3
4
5
6

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 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

#include <iostream>
using namespace std;
const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u) {
  if (u == n) {
    for (int i = 0; i < n; i++) printf("%d ", path[i]);
    puts("");
    return;
  }
  
  for (int i = 1; i <= n; i++) {
    if (!st[i]) {
      path[u] = i;
      st[i] = true;
      dfs(u + 1);
      st[i] = false;
    }
  }
}

int main() {
  cin >> n;
  
  dfs(0);
  
  return 0;
}

n-皇后问题

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

n-queen

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例：

1

4

输出样例：

1
2
3
4
5
6
7
8
9

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

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

#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
  if (u == n) {
    for (int i = 0; i< n; i++) puts(g[i]);
    puts("");
    return;
  }
  
  for (int i = 0; i < n; i++) {
    if (!col[i] && !dg[u + i] && !udg[n - u + i]) {n
      g[u][i] = 'Q';
      col[i] = dg[u + i] = udg[n - u + i] = true;
      dfs(u + 1);
      col[i] = dg[u + i] = udg[n - u + i] = false;
      g[u][i] = '.';
    }
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      g[i][j] = '.';
  
  dfs(0);
  
  return 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

#include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
  if (y == n) y = 0, x++;
  
  if (x == n) {
    if (s == n) {
      for (int i = 0; i < n; i++) puts(g[i]);
      puts("");
    }
    return;
  }
  
  /* 不放 */
  dfs(x, y + 1, s);
  
  /* 放皇后 */
  if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
    g[x][y] = 'Q';
    row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
    dfs(x, y + 1, s + 1);
    row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    g[x][y] = '.';
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      g[i][j] = '.';
  
  dfs(0, 0, 0);
  
  return 0;
}

BFS 宽度优先算法

用途：边权为1时求最短路

走迷宫

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

1
2
3
4
5
6

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

1

8

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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

typedef pair<int, int> PII;

int n, m;
int g[N][N];
int d[N][N];
PII q[N * N], pre[N][N]; // 如果想输出路径，记录一个pre数组即可

int bfs() {
  int hh = 0, tt = 0;
  q[0] = {0, 0};
  
  memset(d, -1, sizeof(d));
  d[0][0] = 0;
  
  while (hh <= tt) {
    auto t = q[hh++];
    
    for (int i = 0; i < 4; i++) {
      int x = t.first + dx[i], y = t.second + dy[i];
      if (x >= 0 && x < n && y >= 0 && y < m && !g[x][y] && d[x][y] == -1) {
        d[x][y] = d[t.first][t.second] + 1;
        // pre[x][y] = t; 
        q[++tt] = {x, y};
      }
    }
  }
  
  /*
  int x = n - 1, y = m - 1;
  while (x || y) {
    cout << x << ' ' << y << endl;
    auto t = pre[x][y];
    x = t.first, y = t.second;
  }
  */
  
  return d[n - 1][m - 1];
}

int main() {
  cin >> n >> m;
  
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> g[i][j];
  
  cout << bfs() << endl;
  
  return 0;
}

有向图

0. 存储方式

  1. 邻接矩阵，空间复杂度O(n2)，适合稠密图
  2. 邻接表，每一个点开一个单链表，链表为该点能到达的点，无顺序要求
1
2
3
4
5
6
7
8
9
10
11

const int = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;

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

int main() {
  memset(h, -1, sizeof(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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];

void dfs(int u) {
  st[u] = true; // 已经被搜过了
  
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    if (!st[j]) dfs(j);
  }
}

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

int main() {
  memset(h, -1, sizeof(h));
}

例：数的重心

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤105

输入样例

1
2
3
4
5
6
7
8
9

9
1 2
1 7
1 4
2 8
2 5 
4 3
3 9
4 6

输出样例：

1

4

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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];

int ans = N;

/* 返回以u为根的子数中点的数量 */
int dfs(int u) {
  st[u] = true;
  
  int sum = 1, res = 0;
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    if (!st[j]) {
      int s = dfs(j);
      res = max(res, s);
      sum += s;
    }
  }
  
  res = max(res, n - sum);
  
  ans = min(ans, res);
  return sum;
}

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

int main() {
  cin >> n;
  memset(h, -1, sizeof(h));
  
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    add(a, b), add(b, a);
  }
  
  dfs(1);
  
  cout << ans << endl;
  
  return 0;
}

2. 图的BFS

### 图中的层次点

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围

1≤n,m≤105

输入样例：

1
2
3
4
5
6

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];

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

int bfs() {
  int hh = 0, tt = 0;
  q[0] = 1;
  
  memset(d, -1, sizeof(d));
  
  d[1] = 0;
  
  while (hh <= tt) {
    int t = q[hh++];
    
    for (int i = h[t]; i != -1; i = ne[i]) {
      int j = e[i];
      if (d[j] == -1) {
        d[j] = d[t] + 1;
        q[++tt] = j;
      }
    }
  }
  
  return d[n];
}

int main() {
  cin >> n >> m;
  
  memset(h, -1, sizeof(h));
  
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    add(a, b);
  }
  
  cout << bfs() << endl;
  
  return 0;
}

3. 有向图的拓扑序列

有向无环图又被称为拓扑图，一个有向无环图一定存在一个入度为0的点

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围

1≤n,m≤105

输入样例：

1
2
3
4

3 3
1 2
2 3
1 3

输出样例：

1

1 2 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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];

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

bool toposort() {
  int hh = 0, tt = -1;
  
  for (int i = 1; i <= n; i++) {
    if (!d[i])
      q[++tt] = i;
    
  while (hh <= tt) {
    int t = q[hh++];
    
    for (int i = h[t]; i != -1; i = ne[i]) {
      int j = e[i];
      d[j]--;
      if (d[j] == 0) q[++tt] = j;
    }
  }
    
  return tt == n - 1;
}

int main() {
  cin >> n >> m;
  
  memset(h, -1, sizeof h);
  
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    add(a, b);
    d[b]++;
  }
  
  if (toposort()) {
    for (int i = 0; i < n; i++) printf("%d ", q[i]);
  } else puts("-1");
  
  return 0;
}

最短路

  • 单源最短路：从一个点到其他所有点的最短路
    • 所有边权都是正数
      • 朴素Dijkstra算法：时间复杂度O(n2)，适用于稠密图
      • 堆优化版Dijkstra算法：时间复杂度O(mlogn)，适用于稀疏图
    • 存在负权边
      • Bellman-Ford：时间复杂度O(nm)
      • SPFA：一般情况下O(m)，最坏O(nm)
  • 多源汇最短路：起点终点不定
    • Floyd算法：时间复杂度O(n3)

朴素Dijkstra算法

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500, 1≤m≤105, 图中涉及边长均不超过10000。

输入样例：

1
2
3
4

3 3
1 2 2
2 3 1
1 3 4

输出样例：

1

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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505;

int n, m;
int g[N][N]; // 稠密图使用邻接矩阵
int dist[N];
bool st[N];

int dijkstra() {
  memset(dist, 0x3f, sizeof dist);
  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;
    
    st[t] = true;
    
    /* 更新最短距离 */
    for (int j = 1; j <= n; j++)
      dist[j] = min(dist[j], dist[t] + g[t][j]);
  }
  
  if (dist[n] == 0x3f3f3f3f) return -1;
  else return dist[n];
}

int main() {
  scanf("%d%d", &n, &m);
  
  memset(g, 0x3f, sizeof g);
  
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    g[a][b] = min(g[a][b], c);
  }
  
  int t = dijkstra();
  
  printf("%d\n", t);
  
  return 0;
}

堆优化Dijkstra算法

手写堆、优先队列

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n,m≤1.5×105, 图中涉及边长均不小于 0，且不超过 10000。 数据保证：如果最短路存在，则最短路的长度不超过 109。

输入样例：

1
2
3
4

3 3
1 2 2
2 3 1
1 3 4

输出样例：

1

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
54
55
56
57
58
59
60
61
62
63

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 150010;

typedef pair<int, int> PII;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

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

int dijkstra() {
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  
  /* 使用小根堆来维护未确定距离中最短距离的点 */
  priority_queue<PII, vector<PII>, greater<PII>> heap;
  heap.push({0, 1});
  
  while (heap.size()) {
    auto [distance, ver] = heap.top();
    heap.pop();
    
    if (st[ver]) continue;
    
    st[ver] = true;
    
    for (int i = h[ver]; i != -1; i = ne[i]) {
      int j = e[i];
      if (dist[j] > distance + w[i]) {
        dist[j] = distance + w[i];
        heap.push({dist[j], j});
      }
    }
  }
  
  if (dist[n] == 0x3f3f3f3f) return -1;
  return dist[n];
}

int main() {
  scanf("%d%d", &n, &m);
  
  memset(h, -1, sizeof h);
  
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }
  
  int t = dijkstra();
  
  printf("%d\n", t);
  
  return 0;
}

Bellman-Ford算法

该算法的存边方式无要求，可以直接定义结构体数组

若图存在负权边且存在负权回路，则最短路为负无穷，而该算法可以求出图中是否有负权回路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

点的编号为 1∼n。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

1≤n,k≤500, 1≤m≤10000, 1≤x,y≤n， 任意边长的绝对值不超过 10000。

输入样例：

1
2
3
4

3 3 1
1 2 1
2 3 1
1 3 3

输出样例：

1

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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edge {
  int a, b, w;
} edges[M];

int bellman_ford() {
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  
  for (int i = 0; i < k; i++) {
    memcpy(backup, dist, sizeof dist); // 备份
    for (int j = 0; j < m; j++) {
      int a = edges[j].a, b = edges[j].b, w = edges[j].w;
      dist[b] = min(dist[b], backup[a] + w);
    }
  }
  
  if (dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f; // 正无穷有可能被负权边更新
  return dist[n];
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  
  for (int i = 0; i < m; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    edges[i] = {a, b, w};
  }
  
  int t = bellman_ford();
  
  if (t == 0x3f3f3f3f) puts("impossible");
  else printf("%d\n", t);
  
  return 0;
}

SPFA算法

只要图中不存在负权回路，即可用SPFA算法

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105, 图中涉及边长绝对值均不超过 10000。

输入样例：

1
2
3
4

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

1

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
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 150010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

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

int spfa() {
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  
  queue<int> q;
  q.push(1);
  st[1] = true;
  
  while (q.size()) {
    int t = q.front();
    q.pop();
    
    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]) {
          q.push(j);
          st[j] = true;
        }
      }
    }
  }
  
  return dist[n];
}

int main() {
  scanf("%d%d", &n, &m);
  
  memset(h, -1, sizeof h);
  
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }
  
  int t = spfa();
  
  if (t == 0x3f3f3f3f) puts("impossible");
  else printf("%d\n", t);
  
  return 0;
}

SPFA判断负环

用一个cnt数组记录到达每个点最短路所需的边数，如果边数大于等于n，则一定有负权回路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围

1≤n≤2000, 1≤m≤10000, 图中涉及边长绝对值均不超过 10000。

输入样例：

1
2
3
4

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：

1

Yes

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

#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010, M = 2 * 1e7 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N], cnt[N], q[M];
bool st[N];

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

int spfa() {
  int hh = 0, tt = -1;
  for (int i = 1; i <= n; i++) {
    q[++tt] = i;
    st[i] = true;
  }
  
  while (hh <= tt) {
    int t = q[hh++];
    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];
        cnt[j] = cnt[t] + 1; // 更新边数
        if (cnt[j] >= n) return true;
        if (!st[j]) {
          q[++tt] = j;
          st[j] = true;
        }
      }
    }
  }
  
  return false;
}

int main() {
  scanf("%d%d", &n, &m);
  
  memset(h, -1, sizeof h);
  
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }
  
  if (spfa()) puts("Yes");
  else puts("No");
  
  return 0;
}

Floyd算法

用邻接矩阵储存所有边

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

1≤n≤200, 1≤k≤n2 1≤m≤20000, 图中涉及边长绝对值均不超过 10000。

输入样例：

1
2
3
4
5
6

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

1
2

impossible
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

#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, INF = 1e9;

int n, m , Q;
int d[N][N];

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] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
  scanf("%d%d%d", &n, &m, &Q);
  
  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--) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    
    d[a][b] = min(d[a][b], w);
  }
  
  floyd();
  
  while (Q--) {
    int a, b;
    scanf("%d%d", &a, &b);
    
    if (d[a][b] > INF / 2) puts("impossible");
    else printf("%d\n", d[a][b]);
  }
  
  return 0;
}

最小生成树

  • Prim算法

    • 朴素版Prim算法（稠密图），时间复杂度O(n2)
    • 堆优化Prim算法（稀疏图），时间复杂度O(mlogn)

  • Kruskal算法，时间复杂度O(mlogm)

Prim算法

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=V，m=E。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

1≤n≤500, 1≤m≤105, 图中涉及边的边权的绝对值均不超过 10000。

输入样例：

1
2
3
4
5
6

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

1

6

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

#include <cstring>
#include <iostream>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim() {
  memset(dist, 0x3f, sizeof dist);
  
  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[t] > dist[j]))
        t = j;
    
    if (i && dist[t] ==  INF) return INF;
    if (i) res += dist[t];
    
    for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);

    st[t] = true;
  }
  
  return res;
}

int main() {
  scanf("%d%d", &n, &m);
  
  memset(g, 0x3f, sizeof g);
  
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    g[a][b] = g[b][a] = min(g[a][b], c);
  }
  
  int t = prim();
  
  if (t == INF) puts("impossible");
  else printf("%d\n", t);
  
  return 0;
}

Kruskal算法

快排+并查集

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=V，m=E。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

1≤n≤105, 1≤m≤2∗105, 图中涉及边的边权的绝对值均不超过 1000。

输入样例：

1
2
3
4
5
6

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

1

6

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

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200010;

int n, m;
int p[N];

struct Edge{
  int a, b, w;
  
  bool operator< (const Edge &e) const {
    return w < e.w;
  }
} edges[N];

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

int main() {
  scanf("%d%d", &n, &m);
  
  for (int i = 0; i < m; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    edges[i] = {a, b, w};
  }
  
  sort(edges, edges + m);
  
  for (int i = 1; i <= n; i++) p[i] = i;
  
  int res = 0, cnt = 0;
  for (int i = 0; i < m; i++) {
    int a = edges[i].a, b = edges[i].b, w = edges[i].w;
    
    a = find(a), b = find(b);
    
    if (a != b) {
      p[a] = b;
      res += w;
      cnt ++;
    }
  }
  
  if (cnt < n - 1) puts("impossible");
  else printf("%d\n", res);
  
  return 0;
}

二分图

二分图存在的充要条件是图中不含奇数环

  • 染色法，时间复杂度O(m + n)
  • 匈牙利算法，时间复杂度O(mn)，实际运行时间远小于此

染色法

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式

如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围

1≤n,m≤105

输入样例：

1
2
3
4
5

4 4
1 3
1 4
2 3
2 4

输出样例：

1

Yes

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

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

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

bool dfs(int u, int c) {
  color[u] = c;
  
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    if (!color[j]) {
      if (!dfs(j, 3 - c)) return false;
    }
    else if (color[j] == c) return false;
  }
  
  return true;
}

int main() {
  scanf("%d%d", &n, &m);
  
  memset(h, -1, sizeof h);
  
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b), add(b, a);
  }
  
  bool flag = true;
  for (int i = 1; i <= n; i++) {
    if (!color[i]) {
      if (!dfs(i, 1)) {
        flag = false;
        break;
      } 
    }
  }
  
  if (flag) puts("Yes");
  else puts("No");
  
  return 0;
}

匈牙利算法

给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式

第一行包含三个整数 n1、 n2 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

输出格式

输出一个整数，表示二分图的最大匹配数。

数据范围

1≤n1,n2≤500, 1≤u≤n1, 1≤v≤n2, 1≤m≤105

输入样例：

1
2
3
4
5

2 2 4
1 1
1 2
2 1
2 2

输出样例：

1

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
50

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

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

bool find(int x) {
  for (int i = h[x]; i != -1; 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;
}

int main() {
  scanf("%d%d%d", &n1, &n2, &m);
  
  memset(h, -1, sizeof h);
  
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b);
  }
  
  int res = 0;
  for (int i = 1; i <= n1; i++) {
    memset(st, false, sizeof st);
    if (find(i)) res++;
  }
  
  printf("%d\n", res);
  
  return 0;
}
Blogging, Algorithm
图论 DFS BFS 拓扑排序 Dijkstra Bellman-Ford Floyd SPFA Prim Kruskal 染色法 匈牙利算法
This post is licensed under CC BY 4.0 by the author.