AcWing 搜素与图论

搜索

DFS

全排列

代码

#include
using namespace std;

int vis[10], a[10];

void dfs(int step, int n)
{
    if (step == n + 1)
    {
        for (int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i]) 
        {
            a[step] = i;
            vis[i] = 1;
            dfs(step + 1, n);
            vis[i] = 0;
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    dfs(1, 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

n-皇后问题

代码

第一种搜索顺序

#include
using namespace std;

const int N = 20;
bool col[N], dg[N], udg[N];
int n;
char g[N][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[i + u] && !udg[n + i - u])
        {
            g[u][i] = 'Q';
            col[i] = dg[i + u] = udg[n + i - u] = true;
            dfs(u + 1);
            col[i] = dg[i + u] = udg[n + i - u] = 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;
}
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
using namespace std;

const int N = 20;
bool row[N], col[N], dg[N], udg[N];
int n;
char g[N][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[n + x - y])
        {
            g[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[n + x - y] = true;
            dfs(x, y + 1, s + 1);
            row[x] = col[y] = dg[x + y] = udg[n + x - y] = false;
            g[x][y] = '.';
        } 
    
}

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;
}
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

BFS

最短路

模板

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

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

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

走迷宫

代码

#include
#include
using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int g[N][N], d[N][N];
int hh, tt = -1, n, m;
PII q[N * N];

int bfs()
{
    q[++tt] = {0, 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];
            // 防止越界  当前位置距离为-1 无障碍时 更新距离
            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;
    
    memset(d, -1, sizeof d);
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
            
    cout << bfs() << 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
47
48
49
50

八数码

分析

用字符串表示状态，哈希表存储当前状态的距离。宽搜x与上下左右元素变换的每一个状态，更新距离，如果搜到终点状态，就返回距离，此距离即为最小变换次数。

代码

#include
#include
#include
using namespace std;

int bfs(string start)
{
    // 终止状态
    string end = "12345678x";
    //哈希表存储距离
    unordered_map<string, int> d;
    //初始化距离
    d[start] = 0;
    queue<string> q;
    q.push(start);
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        int distance = d[t];
        //到达终止距离就返回
        if (t == end) return distance;
        
        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[a * 3 + b]);
                if (!d.count(t))
                {
                    //更新距离
                    d[t] = distance + 1;
                    q.push(t);
                }
                //返回前一步
                swap(t[k], t[a * 3 + 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;
}
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

树与图

模板

邻接表

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);
1
2
3
4
5
6
7
8
9
10
11
12

深度优先遍历

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}
1
2
3
4
5
6
7
8
9
10

树的重心

分析

采用邻接表存储图。采用深度优先遍历，遍历每一个节点，返回当前包括当前节点a的树的节点个数。sum用来记录当前树的节点个数。s表示某一子树的节点个数，res记录子树节点个数的最大值。在记录删去当前节点a所在的树后剩余的节点树，再与ans取最小值即可。

代码

#include
#include
using namespace std;

const int N = 100010, M = 2 * N;
int h[N], e[M], ne[M], idx;
int n;
int ans = N;
bool st[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);
            sum += s;
            // 当前节点子树的最大值
            res = max(s, res);
        }
    }
    
    // 删除该点后其他部分点数的最大值
    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; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    //图当中的编号
    dfs(1);
    
    cout << ans << 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

宽度优先遍历

图中点的层次

分析

数据范围比较小，稀疏图，可以用邻接表进行存储。采用宽度优先搜索，当前距离为-1时，更新距离。

代码

#include
#include
using namespace std;

const int N = 100010;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N], hh, tt = -1, n, m;

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

int bfs()
{
    q[++tt] = 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);
    memset(d, -1, sizeof d);
    
    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
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

有向图的拓扑序列

分析

拓扑序列从入度为0的顶点开始，若去除该点到另一个点的边使得另一个点入度也为0，则这个点也应放到拓扑序列中，用队列来存储拓扑序列，若所有的点都在队列中，则存在拓扑序列，队列的序列即为拓扑序列，反之则不存在拓扑序列。

代码

#include
#include
using namespace std;

const int N = 100010;
int h[N], e[N], ne[N], idx;
int q[N], in[N], hh, tt = -1;
int n, m;

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

bool topsort()
{
    //将所有入度为0的点入队
    for (int i = 1; i <= n; i++)
        if (!in[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];
            //去一条边 入度-1
            in[j]--;
            //入度为0 入队
            if (!in[j]) q[++tt] = j;
        }
    }
    
    return tt == n - 1;
    
}

int main()
{
    cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        //点b的入度+1
        in[b]++;
    }
    
    if (topsort())
    {
        //拓扑序列就是队列的顺序
        for (int i = 0; i <= tt; i++) cout << q[i] << ' ';
        cout << endl;
    }
    else cout << -1;
    
    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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

最短路

正权图 Dijkstra

n 点数 m边数

稠密图：朴素Dijkstra

稀疏：堆优化

朴素Dijkstra

分析

朴素Dijkstra算法适用于求稠密图的单源最短路径问题，思想是进行n次迭代，每次从所有的未被访问过的点中找一个距离1号点最近的点，标志它被访问过了，再用该点去更新其他点的最短距离。

代码

#include
#include
using namespace std;

const int N = 510;
int g[N][N];
bool vis[N];
int d[N], n, m;

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    
    d[1] = 0;
    
    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && (t == -1 || d[t] > d[j])) t = j;
        }
        
        vis[t] = true;
        
        for (int j = 1; j <= n; j++)
            d[j] = min(d[j], d[t] + g[t][j]);
        
    }
    
    return d[n] == 0x3f3f3f3f ? -1 : d[n];
    
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    
    while (m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        //去重边
        g[x][y] = min(g[x][y], z);
    }
    
    cout << dijkstra() << 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
47
48
49
50
51
52

堆优化Dijkstra

分析

堆优化Dijkstra算法适用于求稀疏图的单源最短路径问题，与朴素Dijkstra相比，堆优化Dijkstra算法用小根堆维护最短路径，采用优先队列实现，提高寻找最短边的效率。队头元素表示最短路径的距离以及当前的点。用队头元素更新其他点的最短路径。

代码

#include
#include
#include
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

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

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

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    //第一关键字为距离， 默认以第一关键字排序
    heap.push({0, 1});
    
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int v = t.second;
        
        //找未被访问的点
        if (st[v]) continue;
        st[v] = true;
        
        for (int i = h[v]; i != -1; i = ne[i])
        {
            int j = e[i];
            //更新最短路径
            if (d[j] > d[v] + w[i])
            {
                d[j] = d[v] + w[i];
                heap.push({d[j], j});
            }
        }
    }
    
    return d[n] == 0x3f3f3f3f ? -1 : d[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);
    }
    
    cout << dijkstra() << 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

负权图 bellman-ford

n次迭代，枚举所有的边，松弛最短路径

时间复杂度 O(nm), n表示点数，m表示边数

注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。

如果题目限制经过k条边求最短路径，只能用bellman-ford算法，可以有负环

模板

int n, m;       // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
bool f;

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    // 迭代不超过n条边
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[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

有边数限制的最短路

分析

备份数组的作用： 由于本题有边数的限制，不加备份的话可能会发生串联，如经过一条边求最短路径，1->2 : 1，1->3 ：3，2->3 : 1，则有可能算出1->2->3 ：2， 不满足经过一条边求最短路径的限制，所以只能用上一次的结果进行更新，而不能用当前的结果进行更新，所以需要备份。

为什么这么判断：if (d[n] > 0x3f3f3f3f / 2) f = true;

因为存在负权边，比如1到不了5，1到5的距离为正无穷，1到不了n，1到n的距离为正无穷，5到n的距离为-2， 5把n的距离更新为无穷减去一个数，所以不能直接与无穷相比。在本题中，假设所有的边都为负权边，无穷加上所有的负权仍大于0x3f3f3f3f / 2，则不存在最短路径。

代码

#include
#include
using namespace std;

const int N = 510, M = 100010;

int d[N], backup[N];
struct Edge
{
    int a, b, w;
} edges[M];
int n, m, k;
bool f;

int bellman_ford()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    
    for (int i = 0; i < k; i++)
    {
        memcpy(backup, d, sizeof d);
        for (int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            d[b] = min(d[b], backup[a] + w);
        }
    }
    
    if (d[n] > 0x3f3f3f3f / 2) f = true;
    return d[n];
    
}

int main()
{
    cin >> n >> m >> k;
    
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        edges[i] = {x, y, z};
    }
    
    int t = bellman_ford();
    
    if (f) puts("impossible");
    else cout << t << 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
47
48
49
50
51
52

负权图 spfa

正权图负权图都可以使用，但有可能被卡。

模板

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        //拿更新过的边去更新别的边
        auto 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])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    // 不存在最短路径
    if (dist[n] == 0x3f3f3f3f) f = true;
    return dist[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

spfa求最短路

分析

spfa是优化了的bellman-ford算法，每次拿更新过的点去更新其他点的距离。

代码

#include
#include
using namespace std;


const int N = 100010;

int h[N], e[N], ne[N], w[N], idx;
int q[N], hh, tt = -1;
int d[N];
bool st[N];
int n, m;

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

int spfa()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    
    q[++tt] = 1;
    st[1] = 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 (d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if (!st[j])
                {
                    q[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }
    
    return d[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();
    
    // 不需要d[n] > 0x3f3f3f3f / 2的条件
    // 因为队列里都是由起点更新到的点，不存在bellman-ford算法中未更新的点同样被边更新的情况
    if (t == 0x3f3f3f3f) puts("impossible");
    else cout << t << 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
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

spfa判断负环

分析

在计算过程中维护cnt数组，用来表示1到该点的边数，如果边数大于等于n时，则经过n+1的点，由于抽屉原理，经过了相同的点，可以判断有负环。因为不是判断1到其他点的负环，而是判断有负环，一开始要把所有的点加入队列中。

代码

#include
#include
using namespace std;


const int N = 10010;

int h[N], e[N], ne[N], w[N], idx;
int q[N], hh, tt = -1;
int d[N], cnt[N];
bool st[N];
int n, m;

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


// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化d数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+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 (d[j] > d[t] + w[i])
            {
                d[j] = d[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;
}
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

Floyd求最短路

代码

#include 
using namespace std;

const int N = 210, inf = 1e9;
int d[N][N];
int n, m, k;

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, &k);
    
    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;
        }
        
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = min(d[x][y], z);
    }
    
    floyd();
    
    while (k--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > inf / 2) puts("impossible");
        else printf("%d\n", d[x][y]);
    }
    
    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

最小生成树

Prim

思想： 初始化所有点的距离为无穷，找到集合外距离集合最近的点t，用t更新其他点到集合的距离，并对该点打标记。跟朴素Dijkstra算法思想类似。

代码

#include 
#include  
using namespace std;

const int N = 510, inf = 0x3f3f3f3f;
int g[N][N], d[N];
bool st[N];
int n, m;

int prim()
{
    memset(d, 0x3f, sizeof d);
    
    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 || d[t] > d[j])) t = j;
            
        //如果不是第一个点 并且找到的最小点的距离为inf, 则不构成最小生成树
        if (i && d[t] == inf) return inf;
        //如果不是第一个点, d[t]表示当前点与某一点连线的长度
        if (i) res += d[t];
        
        // 先加上，再更新，否则t=j时，自环更新长度
        for (int j = 1; j <= n; j++) d[j] = min(d[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;
}
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

Kruskal

适合稀疏图

Kruskal算法求最小生成树

代码

#include
#include
using namespace std;

const int N = 100010, M = 2 * N;
int p[N], n, m;
struct Edge
{
    int a, b, w;
    
    bool operator< (const Edge &edge)const
    {
        return w < edge.w;
    }
}edges[M];

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 = 1; i <= n; i++) p[i] = i;
    
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edges[i] = {u, v, w};
    }
    
    sort(edges, edges + m);
    
    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 b 是否在一个集合内
        a = find(a), b = find(b);
        if (a != b)
        {
            res += w;
            cnt++;
            p[a] = b;
        }
    }
    
    if (cnt < n - 1) puts("impossible");
    else printf("%d", res);
    
    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
48
49
50
51
52
53
54
55
56
57

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rKRg9CVK-1669449443875)(%E7%AC%AC%E4%B8%89%E7%AB%A0%20%E6%90%9C%E7%B4%A2%E4%B8%8E%E5%9B%BE%E8%AE%BA.assets/image-20221121081051462.png)]

二分图

**性质：**一个图是二分图当且仅当图中不含有奇数环。

判定二分图

染色法判定二分图

分析

深度优先遍历所有未染色的点，对其染色，如果染色不成功就说明不是二分图。

代码

#include
#include
using namespace std;

const int N = 100010, M = 2 * N;
int h[N], e[M], ne[M], idx;
int color[N];
int n, m;

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

// 判断u染c是否染色成功，默认c 为1 2
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 u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    
    bool f = true;
    
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            //先染1号颜色
            if (!dfs(i, 1))
            {
                f = false;
                break;
            }
        }
    }
    
    printf((f ? "Yes" : "No"));
    
    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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

二分图最大匹配

思想： 从前往后遍历所有的点，找与其可以匹配的点，如果当前遍历到的点a与可以匹配的点b已经与前面的点c相匹配，则判断c能否与另一点d匹配,如果可以，则a匹配b，c匹配d。

二分图的最大匹配

代码

#include
#include
using namespace std;

const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
int match[N], n1, n2, m;
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] || 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 u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    
    int res = 0;
    
    for (int i = 1; i <= n1; i++)
    {
        // 每次模拟匹配的预定情况都是不一样的,所以每轮模拟都要初始化
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }
    
    printf("%d", res);
    
    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
48
49
50
51
52
53
54
55
56
57
58
59
60
61