dfs

img

列出 1-n 的全排列

img

  1. 该数有 0,1,2…n 层
  2. 第 n 层是排列的第 n 个数 0 不算
  3. 从 0 开始深搜 u = n 时打印
  4. st[N] 用于判断第 i 个数是否用过 i 为 st 索引
  5. 注意恢复现场 回溯后都一样
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 <bits/stdc++.h>
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++) cout << path[i] <<' ';
        puts("");
        return;
    }
    // 枚举1-n 没有被用过进入
    for (int i = 1; i <= n; i++) {
        if(!st[i]){
            // 第u层放第u个数  放入i
            path[u] = i;
            // 状态处理  该数被用过
            st[i] = true;
            // 处理第u + 1个数
            dfs(u + 1);
            st[i] = false;
        }
    }

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

    return 0;
}

n 皇后问题

img

  1. col dg udg 分别表示列 正斜线 反斜线 是否放了皇后
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
// #include <bits/stdc++.h>
#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;
    }
    // 枚举1-n 没有被用过进入
    for (int i = 0; i < n; i++) {
        // 截距 y = -x + b
        if(!col[i] && !dg[u + i] && !udg[n - u +i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            // 处理第u + 1个数
            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;
    }

八皇后

https://client.vpn.nuist.edu.cn/https/webvpn893ff9021738b0357186c0f23fc2aed6e24ca283e886022bc5d861ea12f03963/course/85/problem/1220

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
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
// #define int long long

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;

const int N  = 20;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

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

void dfs(int u)
{
	if(u > n)
	{
		res ++;
		return;
	}

	int flag = 1;
	for(int i = 1; i <= n; i ++) // 这一行
		if(g[u][i])
		{
			flag = 0;
			break;
		}


	if(flag)
	{
			for(int i = 1; i <= n; i++)
			{
				if(!col[i] && !dg[i + u - 1] && !udg[i - u + n])
				{
					g[u][i] = 1;
					col[i] = dg[i + u - 1] = udg[i - u + n] = true;
					dfs(u + 1);
					col[i] = dg[i + u - 1] = udg[i - u + n] = false;
					g[u][i] = 0;
				}
			}
	}
	else
		dfs(u + 1);
}

int main()
{
	ios::sync_with_stdio(false);
	n = 8;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++)
		{
			cin >> g[i][j];
			if(g[i][j])
			{
				col[j] = dg[i + j - 1] = udg[j - i + n] = true;
			}
		}
	dfs(1);
	cout << res << endl;

    return 0;
}

bfs

dp 是特殊的最短路径问题

一层一层扩展 +1

核心思想

img

走迷宫

左上角到右下角 求最短路径

img

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100;
typedef pair<int, int> PII;

int g[N][N];   // 地图
int d[N][N];   // 距离
int n, m;
PII q[N*N];

// 手写队列法
int bfs(){
    int hh = 0, tt = 0;
    q[0] = {0, 0};

    memset(d, -1, sizeof d);   //初始化距离  -1 没走过  起点为0
    d[0][0] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while(hh <= tt){
        PII 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]==0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x, y};
            }
        }
    }
    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;
}
// stl法
int bfs(){
    queue<PII> q;
    q.push({0, 0});

    memset(d, -1, sizeof d); //初始化距离  -1 没走过  起点为0
    d[0][0] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 上 右 下 左
    while(q.size())  // 当队列不为空  即走到底无法再走
    {
        auto t = q.front();
        q.pop();    // 不要忘记pop
        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]==0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}

img

八数码

img

思路

  1. 状态表示

  2. queue <string> 存储每一步状态 将表展开成字符串

  3. unorderd_map <string,int> 哈希存储 dist 每一种走法距离开始变换了多少步

  4. 状态转移 ： string - >3 x 3 - > string

img

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 <bits/stdc++.h>
using namespace std;

int bfs(string start){
    string end = "12345678x";
    queue<string> q;    // 存储每一种变换
    unordered_map<string, int> d;  // 存储每一种变换用了多少步

    q.push(start);
    d[start] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        int distance = d[t];
        if(t == end)  return distance;
        // 状态转移
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if( a >= 0 && a < 3 && b >= 0 && b<3){
                swap(t[k], t[3 * a + b]);
                if(!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[k], t[3 * a + b]);
            }
        }
    }
    return -1;
}


int main(){
    string start;
    for (int i = 0; i < 9; ++i) {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start) << endl;

    return 0;
}

矩阵距离 （多远最短路径）

img

题意

找出 01 矩阵中 所有 0 到 1 的最短距离

img

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
int d[N][N];

void bfs(){
    memset(d, -1, sizeof d);

    queue<PII> q;
    for (int i = 0; i < n;i++)
        for (int j = 0; j < m;j++)
            if (g[i][j] == '1')
            {
                q.push({i, j});
                d[i][j] = 0;
            }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int a = t.first;
        int b = t.second;
        for (int i = 0; i < 4;i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if(x >= 0 && x < n && y >=0 && y < m && d[x][y] == -1)
            {
                d[x][y] = d[a][b] + 1;
                q.push({x, y});
            }
        }
    }
}
// 3 4
// 0001
// 0011
// 0110

// 3 2 1 0
// 2 1 0 0
// 1 0 0 1
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];
        // scanf("%s",g[i]);
    bfs();
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++)
            cout << d[i][j]<< ' ';
        puts("");
    }

    return 0;
}

此题注意输入 用 char 整行输入

直接输入

1
2
3
4
5
6
7
8
9
string line;
    while(getline(cin,line))
    {
        int k=0;
        stringstream ssin(line);
        while(ssin>>g[n][k]) k++;
        m=k;
        n++;
    }

数图 dfs

图的存储

imgimg

搜索遍历

  1. 深搜

img

重边和自环

img

树的存储

树 是特殊的图：树是无环连通图

1
2
3
4
5
6
7
8
9
10
const int N = 100010, M = N * 2;
int n, m;
// n个链表头（相当于n个head）  e是结点值 ne是next指针
int h[N], e[M], ne[M],idx;
bool st[N];
// a 插向 b
void add(int a,int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
memset(h,-1,sizeof h);

树的重心

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

下图 删除 4 后 剩下 12857 39 6 连通块数量最大 5

  • 深搜特点 时间复杂度 O（n + m）

    • 比如 4 会返回子树 3,9 6 的 size 剩余 size = n - 2 - 1

img

例题

img

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 <iostream>
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = N * 2;
int n;
// n个链表头  e是结点值 ne是next指针
int h[N], e[M], ne[M],idx;
bool st[N];

int ans = N;

// a 指向 b
void add(int a,int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 返回以u为根子树的大小
int dfs(int u){
    st[u] = true;   // 标记一下已经被搜过了
    // sum表示从一开始  size删掉这个点每一个连通块最大值
    int sum = 1, res = 0;  // res存放子树最大值
    for (int i = h[u]; i != -1;i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j);  // 当前子树大小size
            res = max(res, s);  // 当前子树是连通块  取max
            sum += s;    // 加上各个子树size
        }
    }
    res = max(res, n - sum);  // 删除该点连通块最大点数
    ans = min(ans, res);
    return sum;
}
// 9
// 1 2
// 1 7
// 1 4
// 2 8
// 2 5
// 4 3
// 3 9
// 4 6

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

数图 bfs

树 1 走到 n

img

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 <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010, M = N * 2;
int n, m;
// n个链表头  e是结点值 ne是next指针
int h[N], e[M], ne[M],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; // 从1 开始走 1入队
    memset(d, -1, sizeof d);  // 距离初始位 -1 没有走过

    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];
}
// 4 5
// 1 2
// 2 3
// 3 4
// 1 3
// 1 4

// 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);
    }
    cout << bfs() << endl;
    return 0;
}

拓扑序列

性质

  1. 有向图才有拓扑序列 无向图没有
  2. 有向无环图又叫拓扑图
  3. 有环一定没有拓扑序列
  4. 入度 ： 指向自己的边数
  5. 出度： 指向其他数的边数
  6. 拓扑序列一定存在一个入度为 0 的点，将其他点突破掉

img

思路

img

判断拓扑序列并输出（例）

img

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 <algorithm>
#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];  // d记录入度的数目

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

bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n;i++)
        if(d[i]==0)  // 入度为0的点入队
            q[++tt] = i;
    while(hh <= tt)
    {
        auto 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;   // 一共进了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);
        d[b]++;
    }
    if(topsort())
    {
        for (int i = 0; i < n;i++) cout << q[i] << ' ';
        puts("");
    }
    else puts("-1");
    return 0;
}

最短路问题

img

  1. 稠密图用 dijkstra（临接矩阵）
  2. 稀疏用堆优化版（临接表）
  3. 不超过 k 条边 Bellman-Ford
  4. 难点在建图和抽象具体问题 不在于证明

Dijkstra（朴素 稠密图）

memset 说明 🎇

如果用 memset(a,1,20);（实际上与 memset(a,1,5*sizeof(int))结果是一样的）就是对 a 指向的内存的 20 个字节进行赋值，每个都用 ASCⅡ 为 1 的字符去填充，转为二进制后，1 就是 00000001，占一个字节。一个 INT 元素是 4 字节，合一起是 0000 0001,0000 0001,0000 0001,0000 0001，转化成十六进制就是 0x01010101，就等于 16843009，就完成了对一个 INT 元素的赋值了。

https://www.cnblogs.com/handsomecui/p/4723949.html

思路

img

  1. 1 号点距离初始为 0 其他点初始无穷大
  2. 枚举 1-n 个点 t（s 存储是否枚举过） 找到最近的点 用 t 更新其他点距离

例题

img

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
#include <cstring>
#include <iostream>
#include <algorithm>
// #include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];  // 1到各个点的距离
bool st[N];  // 各个点是否确定

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);  // 所有距离正无穷
    dist[1] = 0;  // 1号点

    for (int i = 0; i < n; i++)  // 遍历n遍  即n个数
    {
        int t = -1;
        for (int j = 1;j <= n;j++) // 找到没有确定的点中距离最小的一个
            // 没遍历过  t = -1 当前t不是最短
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);   // j =（1到t   +   t到j）
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    //cout << 0x3f3f3f3f << endl;
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

img

Dijkstra (堆优化 稀疏图)

img

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 <algorithm>
#include <queue>
// #include <bits/stdc++.h>
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;  // 邻接表存储  w权重
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 t = heap.top();
            heap.pop();

            int ver = t.second, dstance = t.first;  // 编号 和 距离
            if(st[ver])  continue;  // 若出现则跳过
            // 用 t 更新其他点
            st[ver] = true;
            for (int i = h[ver]; i != -1;i = ne[i])
                {
                    int j = e[i];
                    if(dist[j] > dstance + w[i])
                    {
                        dist[j] = dstance + w[i];
                        heap.push({dist[j], j});
                    }
                }
        }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

Bellman-Ford

  • 用来判断负环
  • 一般不常用

思路

  1. 遍历两次 从左到右依次遍历
  2. 最后满足三角不等式 dist[b] <= dist[a] + w
  3. 若有赋权回路 此方法不能用 （可以用来找负环 ）img

例题

  • 限制次数 有负环存在最小值

img

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
#include <iostream>
#include <cstring>
#include <algorithm>

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 -1;  // 负权边可能更新dist[n] < INF
    return dist[n];
}
int main(){
    // cout << 0x3f3f3f3f;
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    int t = bellman_ford();
    if(t == -1 && dist[n] != -1) puts("impossible");    // && 解决 1 -> 2 = -1情况
    else cout << t << endl;
    return 0;
}

Spfa

  1. 由 Ford 优化而来dist[b] = min(dist[b],dist[a] + w)
  2. 考虑只有变小的 a 才能更新别人
  3. 用队列做 长得像 Djstra

思路

img

例题

img

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
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
// #include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N],idx;  // 邻接表存储  w权重
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;
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = Spfa();
    if(t == -1 && dist[n]!=-1) cout << "impossible" << endl;
        // dist[n] != -1 防止一条边-1
    else cout << t <<endl;
    return 0;
}

spfa 判断负环

img

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
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
// #include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N],idx;  // 邻接表存储  w权重
int dist[N],cnt[N];  // cnt 存放经过边数 若大于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()
{
    queue<int> q;
    // 把每个点加进去  不是判断第一个点
    for (int i = 1; i <= n;i++)
    {
        st[i] = true;
        q.push(i);
    }
    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];
                // 更新边数
                cnt[j] = cnt[t] + 1;
                if (cnt[j] > n)  return true;

                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if(Spfa()) cout <<"Yes" <<endl;
    else cout << "No" <<endl;
    return 0;
}

floyd

思路

img

  1. 原理基于动态规划
  2. 用临接矩阵存储

例题

img

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210,INF = 1e9; // INF 正无穷
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(){
    // cout << INF << endl;
    cin >> 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;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w);
    }
    floyd();
    while(Q--){
        int a, b;
        cin >> a >> b;
        if(d[a][b] > INF / 2) cout <<"impossible" <<endl;  // 负权边可能到时1e9 - n
        else cout << d[a][b]<< endl;
    }

    return 0;
}

最小生成树

img

prim 算法 （稠密图）

思路

  • 注意：与 dijstra 区别 prim 用 t 更新的是到集合的距离
  • dj 更新的是到起点的距离
  • 点到集合距离： 点到集合里的点距离最小值
  • img
  • 从 1 开始更新 2,3,4： （1 没有到集合的边，自己当做森林起始） 1 变绿色
  • 用 1， 2 （在连通块）更新： 3,4 到 2 为 2 和 （无） 不用更新 ，2 变绿色
  • 最后都是绿色时，1 集合的距离连线是最小生成树
  • 注： 最小生成树中边的环正负无影响
  • img
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
#include <iostream>
#include <cstring>
#include <algorithm>
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]);  // 用t更新其他点，即到目前树的距离
        st[t] = true;  // t点加入树
    }
    return res;
}
int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] =  min(g[a][b], c);  // 无向图
    }
    int t = prim();
    t == INF ? puts("impossible") : printf("%d", t);
    return 0;
}

kruscal （稀疏图）

思路

  1. 并查集

img

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 <iostream>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;  // 边数是N的2倍******************

int n, m;
struct Edge {
    int a, b, w;
    bool operator < (const Edge &e)  // 从小到大排序
    {
        return w < e.w;
    }
}edge[N];
int p[N];

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

void kruskal()
{
    sort(edge, edge + 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 = edge[i].a, b = edge[i].b, w = edge[i].w;
        a = find(a), b = find(b);
        if(a != b)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    // cout << cnt;
    if(cnt == n - 1) cout << res << endl;  // 存在最小生成树cnt == n - 1!!!
    else cout << "impossible" << endl;
}

int main()
{

    cin >> n >> m;
    for(int i = 0; i < m; i ++)
        cin >> edge[i].a >> edge[i].b >> edge[i].w;

    kruskal();
    return 0;
}

染色法判断二分图

思路

  1. 二分图：划分成两个集合，集合内部没有边
  3. 性质：一个图为二分图 ： 当且仅当图中不含奇数环 （环的边数是奇数）
  4. 做法：用二分法染色一遍，没有矛盾则是二分图
  5. 0 一定连 1 1 一定连 0 如果有偶数环 矛盾
  • 证明： 假设第一个 点左边 最后推出该点在右边

img

例题

img

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
#include <iostream>
#include <cstring>
#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;  // 如果染色  颜色相同返回false
        }
    return true;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--)
        {
            int a, b;
            cin >> 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;
}

二分图最大匹配

https://blog.csdn.net/u011815404/article/details/84260940

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 = 510, M = 100010;

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

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

bool find(int u) // 男生
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true; // 标记找过  先霸占
            if(!match[j] || find(match[j])) // 该女生没有对象 或者其对象另有其人
            {
                match[j] = u;
                return true;
            }
        }
    }
    return false;
}

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

    cin >> n >> m >> k;
    while(k --)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int res = 0;
    for(int i = 1; i <= n; i ++)
    {
        memset(st, false, sizeof st);
        if(find(i)) res ++;
    }
    cout << res << endl;

    return 0;
}