搜索与图论算法

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
31
32
33
34
#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]);
        }
        printf("\n");
        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;
}

dfs类似一个暴力搜索题，就是要找出n的所有数字排列。可以把dfs排列过程想象成一棵树。dfs又叫暴搜，顾名思义就是在一定的条件下进行重复的暴力运算。本质是假定有n个位置，从第一个位置开始依次往下进行搜索，如果该数字未出现则填入并标记为该数字已经出现过了，并继续往下找，直至找完全部数字，此时输出一组答案，然后进行回溯。回溯要注意，不仅仅要回溯上一个位置，同时也要回溯删除掉上一个位置上面数的标记，如果此时没有数可以填了，那么就继续回溯，直至能继续填数为止。
说白了，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
31
32
33
34
35
36
37
38
39
40
41
#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])
        {
            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()
{
    scanf("%d", &n);
    for (int i = 0; i < n;i++)
    {
         for (int j = 0; j < n;j++)
        {
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}

皇后问题的实现，本质上与上一道题没什么区别，判断dfs的条件也差不多，主要是要看能不能解析题意，本题的解释点就是说，在一横列，纵列，斜角都只有一个Q，那么判断条件就从上一个题的判断数字变成了判断坐标，如果该列上存在Q，那么就继续进行下一个数，如果不存在Q，就输出Q然后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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
    }
    
    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] = '.';
    }
    dfs(x, y + 1, s);
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n;i++)
    {
        for (int j = 0; j < n;j++)
        {
            g[i][j] = '.';
        }
    }
    dfs(0, 0, 0);
    return 0;
}

第二种实现方法相比较第一种方法更加直接暴力，方法一是在一列为单位的基础上，而方法二就是暴力搜索，对所有数挨着挨着一个一个搜索。

走迷宫

关于回溯的时候是否要进行减去操作，例如将该点重新标记成未被发现的点或者是算总和的时候是否要把该点对应的值进行减去，主要是看在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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char s[N][N];
bool ss[N][N];
bool st;

void dfs(int x, int y)
{
	if(x == n && y == m)
	{
		st = true;
		return;
	}
	ss[x][y] = true;
	int dx[4] = {1,0,-1,0};
	int dy[4] = {0,1,0,-1};
	for(int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
        int ny = y + dy[i];
		if(s[nx][ny] == '.' && !ss[nx][ny] && nx >= 1 && nx <= n && ny >= 1 && ny <= m)
		{
			dfs(nx,ny);
			ss[nx][ny] = false;
		}
	}
	return;
}
int main() 
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
    	for(int j = 1; j <= m; j++)
    	{
    		cin >> s[i][j];
		}
	}
	dfs(1,1);
	if(st == true)
	printf("Yes\n");
	else 
	printf("No\n");
    return 0;
}

因为在中途我们把回溯的点重新标记成false，这样就会导致在某些时候这个点被反复走过但是又无法到达终点 形成恶性循环。

因为此时我们在void函数中的return是无法直接退出所有递归的，所以这是候大概率我们会代码超时，修改方法也分为两种，第一种是直接去掉重标记，第二种就是换成bool函数，在遇到正确答案的时候直接返回true会直接退出所有函数，但是这种解决方案只能用于判断是否问题，无法解决数量问题，因此我会比较推荐第一种解决方案。下面附上代码。

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<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char s[N][N];
bool ss[N][N];
bool st;

void dfs(int x, int y)
{
	if(x == n && y == m)
	{
		st = true;
		return;
	}
	ss[x][y] = true;
	int dx[4] = {1,0,-1,0};
	int dy[4] = {0,1,0,-1};
	for(int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
        int ny = y + dy[i];
		if(s[nx][ny] == '.' && !ss[nx][ny] && nx >= 1 && nx <= n && ny >= 1 && ny <= m)
		{
			dfs(nx,ny);
//			ss[nx][ny] = false;
		}
	}
	return;
}
int main() 
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
    	for(int j = 1; j <= m; j++)
    	{
    		cin >> s[i][j];
		}
	}
	dfs(1,1);
	if(st == true)
	printf("Yes\n");
	else 
	printf("No\n");
    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
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char s[N][N];
bool ss[N][N];
bool st;

bool dfs(int x, int y)
{
	if(x == n && y == m)
	{
		return true;
	}
	ss[x][y] = true;
	int dx[4] = {1,0,-1,0};
	int dy[4] = {0,1,0,-1};
	for(int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
        int ny = y + dy[i];
		if(s[nx][ny] == '.' && !ss[nx][ny] && nx >= 1 && nx <= n && ny >= 1 && ny <= m)
		{
			if(dfs(nx,ny))
			{
				return true;
			}
		}
	}
	return false;
}
int main() 
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
    	for(int j = 1; j <= m; j++)
    	{
    		cin >> s[i][j];
		}
	}
	if(dfs(1,1))
	printf("Yes\n");
	else 
	printf("No\n");
    return 0;
}

需要重标记

当我们遇到需要重标记的迷宫问题的时候大部分时候我们不会使用dfs来解决，这样的问题一般都是在dp种出现并且可以直接用dp解决。这里就不过多赘述，当然遇到了就回来砍我吧。

求和问题

需要重标记

一般来说走迷宫问题都是用来判断是否的dfs问题，或者有计算数量的情况；
但是求和问题就一定是问我们有关数量的问题。这里就需要分清楚什么时候需要重标记，什么时候不需要重标记。

比如这个猫粮问题，乍一看是不是觉得，这个题是求和问题，应该都需要进行重标记，其实不然，就如我之前所说，是否进行重标记只涉及来路，例如从1到3和从3到1是完全不同的两种结果，但是此题，或者说所有求和问题中，似乎都只存在不涉及来路的问题，比如说1+3和3+1没有任何区别，那么在这种时候如果我们进行重标记的话就会导致遍历紊乱，多算很多次答案，但是我们会发现如果不进行重标记的话，，就会使得答案变少了，真是麻烦。

其实我们会发现这个题其实是需要重标记的但是不是传统的重标记，因为求和的原因，每一次算出sum总和之后我们都应该对sum进行重标记，简单来说就是删除这次加上的和，但是这样的话就会导致另一个问题，就是出现1+3和3+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
#include<bits/stdc++.h>
using namespace std;

const int N = 50;
int n, l, r;
int s[N];
int cnt;

void dfs(int index, int sum) {
    if (sum > r) return;
    if (sum >= l && sum <= r) cnt++;
    
    for (int i = index; i < n; i++) {
        dfs(i + 1, sum + s[i]);
    }
}

int main() {
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    
    dfs(0, 0);
    
    cout << cnt << endl;
    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
43
44
45
46
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010,M=N*2;
int h[N], ne[M], e[M], idx;
int n;
bool st[N];
int ans = N;
void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
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;
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1;i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1);
    printf("%d", ans);
    return 0;
}

此题名为树的重心；题意为有一棵树，找到一根树节点，删去那个树节点后，找到其他所有连通块的点最大值的最小值。这道题就是一道dfs的题，从树根开始，不断往下深搜，在每一个节点找到一个对应的最大值，然后选出其中的最小值。难点：
1、数组建立邻接表
2、dfs的正确实现：
]]

3、无向图中我们应该将临链表进行双向的添加。
4、根据惯性思维，我们很容易直接在dfs函数中返回ans，但是这道题因为dfs会不断递归实现，其实我们要返回的数是第x个点的儿子，所以要返回他的下面的个数。

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 110;
int n, m;
int g[N][N];
int d[N][N];
pii q[N * N];
int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0, 0};
    memset(d, -1, sizeof(d));
    d[0][0] = 0;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};//这里就是4个方向，用坐标表示。
    while(hh<=tt)
    {
        auto t = q[hh++];
        for (int i = 0; i < 4;i++)
        {
            int x = t.first + dx[i];
            int y = t.second + dy[i];//加上4个方向的坐标来达到分别向四周移动的目的。
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)//这里是判断距离为1且没有走过的路径。
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x, y};//将符合条件的路径插入队列。
            }
        }
    }
    return d[n - 1][m - 1];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n;i++)
        for (int j = 0; j < m;j++)
            scanf("%d", &g[i][j]);
    printf("%d", bfs());
    return 0;
}

bfs又称宽搜，与深搜不同，深搜是一条路走到底然后再回头，宽搜是先把每一条路的分支都走一遍，然后再往后走，就是先把同等距离的路走完了再往下继续搜索，这样就能找到最短路径。

下面解释一下代码，这里要运用一个队列（没学过stl只能手搓）。将将队头的数四个方向的离他最近的符合条件的数插入队列并标记，直至走完所有路径。]]

八数码

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

using namespace std;

int bfs(string start)
{
    // 定义目标状态
    string end = "12345678x";
    // 定义队列和dist数组
    queue<string> q;
    unordered_map<string, int> d;
    // 初始化队列和dist数组
    q.push(start);
    d[start] = 0;
    // 转移方式
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        // 记录当前状态的距离，如果是最终状态则返回距离
        int distance = d[t];
        if (t == end)
            return distance;
        // 查询x在字符串中的下标，然后转换为在矩阵中的坐标
        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for (int i = 0; i < 4; i++)
        {
            // 求转移后x的坐标
            int a = x + dx[i], b = y + dy[i];
            // 当前坐标没有越界
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                // 转移x
                swap(t[k], t[a * 3 + b]);
                // 如果当前状态是第一次遍历，记录距离，入队
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                // 还原状态，为下一种转换情况做准备
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    // 无法转换到目标状态，返回-1
    return -1;
}

int main()
{
    string c, start;
    // 输入起始状态
    for (int i = 0; i < 9; i++)
    {
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;

    return 0;
}

八数码是一个极其强大的bfs题，它的本质是宽搜，难点
1、能否想到将二维字符串转化为一维字符串。即为终点值。
2、能否想到在每一个状态使用bfs进行宽搜。
]]
3、能否实现bfs，如何实现每一次行动距离为1。
4、如何正确使用stl。
关于stl，请详细了解stl篇章。
说到底，此题的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
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int h[N], ne[N], e[N], idx;
int q[N], d[N];
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])
        {
            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 (topsort())
    {
        for (int i = 0; i < n; i++)
        {
            printf("%d ", q[i]);
        }
    }
    else
        printf("-1\n");
    return 0;
}

此题的题意为，存在一个有向树，进行排序，使得箭头前面的数总比箭头后面的数后输出。：
]]
补充设定：入度与出度。
入度就是说有多少指向该数字的数。
出度就是说该数字有多少指向其他数字的数。

那么本题的解题思路就是：给定一个队列，在队列中我们存入每一个入度为0的数。然后往下进行bfs宽搜，搜索每一个离他最近的数，然后让它的入度–，直至减到0为止，然后我们就可以输出他，这样就能得到一个入度依次增大的数列，也就是拓补排序数列。
本题难点：
1、关于入度和出度的思想。
2、能否想到使用bfs对每一个数进行更深层次的宽搜。
3、输出时，应当怎样才能把序列输出：这里就是直接使用依次读入队列得数来表示就行了。

最短路问题

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
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
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;
    return dist[n];
}
int main()
{
    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);
    }
    cout << dijkstra() << endl;
    return 0;
}

此题题意为在一个复杂的路径图中，找出点1到点n的最短路径。
Dijkstra算法就是一个不断更新最短路径的做法，具体就是，先进行第一层搜寻，找到最短的路径，然后把这个点代替前面的点，并以此点为最初的点，不断对后面的点进行搜寻的一个做法，本质上也时一个贪心算法。
图-最短路径-Dijkstra(迪杰斯特拉)算法_哔哩哔哩_bilibili
具体情况可以看此视频，我觉得讲的比y总的好……
]]
本题难点：
1、在判断已经找到最短路径之后，我们需要直接pass掉这个数，并且在之后的数都不用指向它的路径。
2、在更新时候的条件判断。
3、代码实现难度巨大，
注意每次更新的时候，要把该点到1的最短距离与新找到的路径距离进行比较找出最小值，如果不存在，即为无穷远。
最外面的for循环相当于是从大到小找出每一个点到1的最短距离，中间的循环中的第一个循环，就是找到最后一个没被标记的点之前的所有距离中比最后一个没被标记的点的距离小的数，然后让temp标记他，最后用于更新。
中间有许多点之间的距离是我们找不到的，其实不用着急，因为我们找的其实都是最小值，而在最开始的地方，我们就把每一个点的值都赋为正无穷，因此那些不存在的点其实都是无穷，无需理会。
代码详解视频1：
https://www.bilibili.com/video/BV1UZ421U7bL/?spm_id_from=333.337.search-card.all.click&vd_source=909a7ee9e9c30d874caa8340df4408a2
代码详解视频2：
https://www.bilibili.com/video/BV1Ya411L7gb/?spm_id_from=333.337.search-card.all.click&vd_source=909a7ee9e9c30d874caa8340df4408a2

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10010, M = 510;
int n, m, k;
int dist[N], backup[N];
struct Edge
{
    int a, b, w;

} edges[M];

int bellman_ford()
{
    memset(dist, 0x3f3f3f3f, 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;
    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();
    cout << t << endl;
 }

此题的思路与dijkstra算法差不多，也是找在一堆有向树中找到1到n的最短距离，不过此题有另外的要求，那就是走过的路径不能超过k条。
本题难点：
1、结构体构造树。
2、求路径的时候，不能使用每次重新遍历的距离，而应该使用前一次保存的距离，因为我们有k的次数限制，所以我们在求此次路段距离的时候不能用此次a点的距离，不然的话在判断过程中我们就只能找到最短距离，而无法找到限制次数的最短距离。

Floyd算法求最短路

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
#include<iostream>
#include<algorithm>
#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()
{
    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)
        {
            printf("impossible\n");
        }
        else
            printf("%d\n", d[a][b]);
    }
    return 0;
}

Floyd算法是一个三层循环的算法，时间复杂度很高，所以是个很笨的算法。
这里需要用到一个动态规划的知识，那就是说假如说从i到j中，我们让他从i到j最多经过从1到k节点，那么也就相当于把他从i到j的距离拆分成了从i到k，再从k到j。d数组表示从i到j的距离吗，当i=j的时候，距离为0。
最后我们使用这种不断遍历的三层循环找出从i到j的最小距离。

Spfa算法求最短路径

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<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100010;
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])
                {
                    st[j] = true;
                    q.push(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;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if(t==-1)
        printf("impossible");
    else
        printf("%d", t);
    return 0;
}

spfa算法本质上是bellman算法的优化版本，因为bellman算法在执行的过程中，会傻乎乎的进行两次for循环，这样十分浪费时间，因此，我们发现，在我们更新距离的时候，如果上一个点的dist值大于这个值的话，那么我们其实根本不需要遍历，因为他一定会大于dist本值，更何况还要加上一个距离，所以我们就想到要使用一个队列，在队列中我们只存入更大的值，然后每一次弹出一个值，直至队列中不存在任何数。这样就能保证每一次我们都进行有效遍历。

本题难点：
1、对dijkstra算法的掌握，因为相似度很高。
2、对bfs宽度搜索的敏锐判断。
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
#include<iostream>
#include<algorithm>
#include<cstring>
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(c==color[j])
                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;
}

染色法判断二分图，首先我们要搞明白什么是二分图。
二分图就是说，在一串数中，能把这一堆数分成两份，相邻的两个点不能分进同一堆，并且不会存在冲突。那么何时会存在冲突呢？就是说如果存在一个奇数环，那么则会存在冲突，为什么这么说呢，看图
]]
如果不存在以上冲突的话，那么就能说明，这是一个二分图。
然后我们再来说说思路，其实也就一目了然了，所谓染色法，就是把相邻的点染成不同的两种颜色，如果存在相邻的点的颜色相同的话，那么就判定为不是二分图。此题可以使用bfs和dfs，但是dfs的代码实现更容易，所以我们选择dfs，在深度搜索中，我们选择将第一个点染成1，然后把下一个点染成2，以此类推，所以每次染色时，下一个点的颜色都是3-c，如果下一个点没有染色，就按照这个来，如果已经染色了，就看看与相邻的点的颜色是否一致，如果一致的话，就判断false。
本题难点：
1、dfs的代码实现
2、无向图双向临链表的输入，以及二倍数组防止爆长度。
3、为了更好的更迭，想到3-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
#include <iostream>
#include <cstring>
#include <algorithm>
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;
}

匈牙利算法是一个能快速找出二分图最大匹配的算法，二分图匹配就是，满足匹配的边中没有任意两条边有共同的顶点。
]]
具体的思路就是，以左边的数为基础，挨着寻找能进行匹配的右边的数（未被匹配过），如果已经被匹配了的话，我们就 先看那个已经被匹配的数，匹配她的那个数是否有其他数能匹配，如果可以的话，就让他去匹配那个数，当然如果他能匹配的其他数也被匹配了的话，那就继续看匹配她的那个数是否有其他数能匹配，依次类推，就是一个递归思想，也就是说，在这样的搜索下，每个数都能找到自己能匹配的最佳的数。在把他们加起来，就是最大的匹配数。
本题难点：
1、递归寻找能匹配的数的思路实现。
2、临链表中开不同数组的大小。

树

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
#include <iostream>
#include <algorithm>
#include <cstring>
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, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b], w);
    }
    int t = Prim();
    if (t == inf)
        puts("impossible");
    else
        printf("%d\n", t);
    return 0;
}

最小生成树的含义是相当于找出连通块内所有距离的总和的最小值。所以其实本题也是使用dijkstra算法求出最短路径，然后再把每条路径加起来，就能算出最小生成树。具体算法与dijkstra相差不大，都是先进行寻找没被遍历过的小于前一个点的点，然后让t等于他然后从t的角度不断更新每一个点的距离，如果不存在就为无穷远。然后在标记t。最后再把dist[t]加进去就完成了。
本题难点：
1、dijkstra算法的实现与运用。
2、无向图在使用时进行双向存数就好。
3、先加dist再更新，防止负环、自环影响结果。

Kruskal算法求最小生成树

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 <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
struct Edge
{
    int a, b, w;
    bool operator<(const Edge &W) const
    {
        return w < W.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;
        cin >> 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)
        printf("impossible");
    else
        printf("%d\n", res);

    return 0;
}

Kruskal算法是一个加边的算法，大致思路为，先将给定的每一条边进行从小到大的排序，然后进行遍历，这里运用并查集的知识，判断两个点是否已经处在一个连通块中，如果存在的话，那么就不管他，人如果不存在的话，我们就把这两个点连入一个连通块中，然后让最终的答案（生成树）加上这个距离，因为我们的距离是从小到大的顺序进行排序的，所以我们这里能直接进行遍历，如果没有就加入，往后一旦存在的话必然比前面这个加入的大，那么就不考虑为最小生成树，如果不存在的话，说明两点之间还没有道路，那么就直接加入，因为这时一定是最小的。
最后进行一次判断，如果存在的边数小于点数-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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];
void add(int a, int b)
{
    e[idx] = b, ne[b] = h[a], h[a] = idx++;
}
int bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = 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];
}
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号点（也就是根节点）到n的最短步数。
那么此时我们就要很敏锐的想到bfs，因为是求最短步数，并且每一小节的距离都为1，所以此时我们可以使用bfs。
本题难点：
1、如何正确实现bfs（bfs模板）：
用一个队列进行模拟即为，依次读取没有入队的数，并且不断距离加一，然后遍历整个树，找到那个n然后输出n的距离即可。
2、有向树的临链表在实现的时候要注意只实现一次add（a，b）。