Acwing算法基础课第三讲总结

自来也sama 收录于类别 Acwing算法基础课

2021-03-05 2021-03-05 约 6953 字预计阅读 14 分钟

本讲主要内容

DFS，BFS，树与图的深度优先遍历，树与图的广度优先遍历，拓扑排序，Dijkstra，bellman-ford，spfa，Floyd，Prim，Kruskal，染色法判定二分图，匈牙利算法。

本章思维导图

DFS（深度优先搜索）

AcWing-842 排列数字

原题链接

思路

基础dfs。库函数也能做，详见文章挑战程序设计竞赛第二章第一节习题总结。
其实如果换成组合数字的问题，也可以当成排列问题来考虑，在排列时是剪枝去重就可以了。

参考代码

#include <cstdio>
const int maxn = 10;

int Permutation[maxn], n;
bool st[maxn];

void dfs(int curPos)
{
    if(curPos == n)
    {
        for(int i = 0; i < n; i++)
            printf("%d ", Permutation[i]);
        printf("\n");
        return ;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!st[i])
        {
            Permutation[curPos] = i;
            st[i] = true;
            dfs(curPos+1);
            st[i] = false;
        }
    }
}

int main(void)
{
    scanf("%d", &n);

    dfs(0);

    return 0;
}

AcWing-843 n-皇后问题

原题链接

思路

dfs。这道题可以穷竭搜索，但是更优的解法是剪枝。
穷竭搜索是每个格子挨个dfs，选择放或者不放，最坏复杂度约为$O(2^{n^2})$；
由于已经放了皇后的行，列以及主，副对角线都不能放，一旦前面的位置有不合法的放置，后面怎么放也不合法，所以可以不用继续递归，直接剪枝即可，最坏复杂度约为$O(n!)$。

参考代码

#include <cstdio>

const int maxn = 20;
char ans[maxn][maxn];
bool col[maxn], leadDiag[maxn], counDiag[maxn];
int n;

void dfs(int curCol)
{
    if(curCol == n)
    {
        for(int i = 0; i < n; i++)
            puts(ans[i]);
        puts("");
        return ;
    }

    for(int i = 0; i < n; i++)  //检查当前行的哪一列可以放元素
    {
        if(!col[i] && !leadDiag[curCol+i] && !counDiag[n+curCol-i])
        {
            ans[curCol][i] = 'Q';
            col[i] = leadDiag[curCol+i] = counDiag[n+curCol-i] = true;
            dfs(curCol+1);
            col[i] = leadDiag[curCol+i] = counDiag[n+curCol-i] = false;
            ans[curCol][i] = '.';
        }
    }
}

int main(void)
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            ans[i][j] = '.';

    dfs(0);

    return 0;
}

BFS（广度优先搜索）

AcWing-844 走迷宫

原题链接

思路

bfs。这里找的是最短路，需要标记下是否第一次达到此位置。

参考代码

#include <iostream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 110;
typedef pair<int, int> PII;
queue<PII> q;
int n, m, maze[maxn][maxn], dis[maxn][maxn];    //dis数组标记是否第一次达到并储存距离
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};   //四个方向移动的向量

int bfs(void)
{
    memset(dis, -1, sizeof(dis));
    dis[0][0] = 0;
    q.push({0, 0});

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

        //利用向量模拟四个方向的移动
        for(int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            //若(x,y)这个点可以到达，并且是第一次到达，则将其加入队列中
            if(x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && dis[x][y] == -1)
            {
                dis[x][y] = dis[t.first][t.second]+1;
                q.push({x,y});
            }   
        }
    }

    return dis[n-1][m-1];   //从起点到终点的移动距离就是移动次数
}

int main(void)
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> maze[i][j];

    cout << bfs() << endl;

    return 0;
}

AcWing-845 八数码

原题链接

思路

bfs。把每一个状态抽象为一个节点，终状态即为“迷宫”的终点这道题就转化为球起点到终点的最短距离，显然用BFS 达不到的状态就输出-1，即只需要检查达到的所有状态中有没有终状态，若没有就输出-1。

参考代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;

//使用string在一维记录状态，unordered_map作为哈希，标记当前状态是否为第一次达到并记录达到当前状态需要从初状态进行变换的次数
queue<string> q;
unordered_map<string, int> dis;
string st;
//而状态转移需要在二维进行，仍然用向量来模拟
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

int bfs(string st)
{
    string ed = "12345678x";
    dis[st] = 0;
    q.push(st);

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

        //到达了终状态就返回距离
        if(t == ed) return dis[t];

        int disTmp = dis[t];
        for(int i = 0; i < 4; i++)
        {
            int k = t.find('x');
            //一维转化到二维进行状态转移
            int x = (k/3)+dx[i], y = (k%3)+dy[i];
            if(x >= 0 && x < 3 && y >= 0 && y < 3)
            {
                //将状态的转移反映在一维下，检查是否第一次到达该状态并记录与初状态的“距离”
                swap(t[x*3+y], t[k]);
                if(!dis.count(t)) 
                {
                    dis[t] = disTmp + 1;
                    q.push(t);
                }
                //注意将状态复原，因为这里需要每一可能的状态，而交换状态都是从当前初状态进行交换的
                swap(t[x*3+y], t[k]);
            }
        }
    }

    //达到不了返回-1
    return -1;
}

int main(void)
{
    for(int i = 0; i < 9; i++)
    {
        char ch;
        cin >> ch;
        st += ch;
    }

    cout << bfs(st) << endl;
    return 0;
}

树与图的深度优先遍历

AcWing-846 树的重心

原题链接

思路

树与图的深度优先遍历模板题。使用邻接表时，一定记得初始化头指针为空。
另外，这里是无向图，用有向图的方式存储无向图对于边数来说，需要两倍的大小。图的存储主要就是存结点之间的边，有时会开一个新的空间存储权重（边的距离之类的）。
时间复杂度为$O(n+m)$，其中n为点数，m为边数。

参考代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 100010, maxm = 2 * maxn;
int h[maxn], ne[maxm], e[maxm], idx; //有向图的存储方式来存储n个点共有2n-2条边
bool st[maxn];
int res = maxn, n;

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

int dfs(int u)
{
    st[u] = true;

    //sum为包含当前结点的连通块点的数目，sz为当前结点的子连通块中点的数目的最大值
    int sum = 1, sz = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int t = e[i];
        if(!st[t])
        {
            int s = dfs(t); //s为当前结点子连通块的点的数目
            sz = max(sz, s);
            sum += s;
        }
    }
    sz = max(sz, n - sum);  //由于是单链表存储，当前结点上面（前面）的连通块需要用总数减去当前结点及其连通块的点数和
    res = min(sz, res);

    return sum;
}

int main(void)
{
    cin >> n;
    memset(h, -1, sizeof(h));   //记住初始化头结点的指针为空
    for(int i = 0; i < n - 1; i++)  //注意树是不存在环的，即n个点只有n-1条边
    {
        int x, y;
        cin >> x >> y;
        add(x, y), add(y, x);
    }

    dfs(1); //这里从哪个结点开始都可以，但要注意结点编号是从1开始的
    cout << res << endl;

    return 0;
}

树与图的广度优先遍历

AcWing-847 图中点的层次

原题链接

思路

树与图的广度优先遍历模板题。和宽搜类似的思路，用到了队列。
这道题主要利用了宽搜能够搜到最短路径的特点。这里的自环对长度的影响可以忽略，因为边权都为非负数，显然不会考虑到自环。而对于重边，则只需要在读入时保留最短的那条边即可。
时间复杂度为$O(n+m)$，其中n为点数，m为边数。

参考代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 100010;
int h[maxn], ne[maxn], e[maxn], idx;
int dis[maxn];
int n, m;
queue<int> q;

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

int bfs()
{
    //下面就是和走迷宫一样的思路，这里迷宫变成了多个链表
    memset(dis, -1, sizeof(dis));    
    dis[1] = 0; 
    q.push(1);

    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dis[j] == -1)
            {
                dis[j] = dis[t] + 1;
                q.push(j);
            }
        }
    }

    return dis[n];
}

int main(void)
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));   //记得初始化单链表头结点指针为空
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    cout << bfs() << endl;

    return 0;
}

拓扑排序

AcWing-848 有向图的拓扑序列

原题链接

思路

树与图的广度优先遍历的一种应用。
复杂度为$O(n+m)$，其中n表示点数，m表示边数。

参考代码

#include <cstdio>
#include <cstring>

const int maxn = 100010;
int h[maxn], ne[maxn], e[maxn], w[maxn], idx;   //数组w存储的权为图中结点的入度
int q[maxn], tt = -1, hh;
int n, m;

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

bool topo_sort()
{
    //让图中入度本来为0的结点入队
    for(int i = 1; i <= n; i++)
        if(w[i] == 0)
            q[++tt] = i;

    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            w[j]--; //从当前路径搜到的点入度减一
            if(w[j] == 0) q[++tt] = j;
        }
    }

    //队头起始坐标为0，所以全部点都入队时队尾的值应为n-1，全部入队则说明有拓扑序列
    return tt == n - 1;
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof(h));   //别忘记初始化链表头结点指针为空
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        add(x, y);
        w[y]++;
    }

    if(topo_sort())
    {
        for(int i = 0; i < n; i++)
            printf("%d ", q[i]);
        printf("\n");
    }
    else
        printf("-1\n");

    return 0;
}

Dijkstra

AcWing-849 Dijkstra求最短路Ⅰ

原题链接

思路

Dijkstra算法的应用。这道题是稠密图，所以应该用邻接矩阵存储，两个下标分别对应边的两个结点，而数组中元素的值则为边权。
稠密图的边数比较多，而结点数比较少，从而应该用朴素Dijkstra算法，它的时间复杂度为$O(n^2 + m)$，其中n为结点数，m为边数。
这个算法主要利用了贪心的思想，总共迭代n次。步骤如下：

在所有未确定最短距离的点中找到找到距起点最短的点。
利用找到的这个点来更新起点到各点的距离。
经过n次这样的迭代后，就得到了起点到每个点的最短距离。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

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

int dijkstra()  //利用了贪心的思想
{
    //初始化起点距离和起点到各点距离
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; 

    for(int i = 0; i < n; i++)  //迭代n次（这里并不是按点的编号顺序确定最小值的，迭代一次就找到一个最小值，所以n-1次也可以，因为第一个点的距离是已经确定的，）
    {
        int t = -inf; //标记为-inf表示还没找到点
        for(int j = 1; j <= n; j++)    //在还没有确定最短距离的点当中寻找距离起点最近的点
            if(!st[j] && (t == -inf || dis[t] > dis[j]))    //若还没找到点，则直接赋值，否则比较和起点的距离，保留距离更小的那个点
                t = j;

        for(int j = 1; j <= n; j++)
            dis[j] = min(dis[j], dis[t] + g[t][j]); //利用t来更新起点到各点距离的最小值

        st[t] = true;   //标记该点已经确定了到起点的最短距离
    }

    return dis[n];
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);  
        g[x][y] = min(g[x][y], z);  //由于权值非负，自环在这道题可以忽略不计，但对于重边，应仅保留最短的边
    }
    int t = dijkstra()
    if(t == inf) printf("-1\n");
    else printf("%d\n", t);

    return 0;
}

AcWing-850 Dijkstra求最短路Ⅱ

原题链接

思路

这道题是稀疏图，对于稀疏图应该使用堆优化的Dijkstra算法，注意这里使用的堆是STL中现成的，并且是小根堆。步骤仍然和朴素Dijkstra算法类似，只不过“在还没有确定最短距离的点当中寻找距离起点最近的点” 这一步中，由于堆中取最小的点的复杂度为$O(1)$，而堆改变每一个点的复杂度为$O(logn)$，优化过后，Dijkstra算法的复杂度就变成了$O(mlogn)$，其中n为点数，m为边数。
另外，在建堆时应该注意，这里堆中的元素是pair，而我们希望以距离的长短来排列堆中的元素，所以要把起点到每个点的距离放在pair中的第一个位置，而结点坐标放在第二个位置。

参考代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

const int maxn = 150010;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> PII;
int h[maxn], ne[maxn], e[maxn], idx;
int w[maxn], dis[maxn];
bool st[maxn];
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(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({dis[1], 1});

    //下面类似宽搜
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int v = t.second, d = t.first;

        if(!st[v])
        {
            st[v] = true;
            for(int i = h[v]; i != -1; i = ne[i])
            {
                int j = e[i];
                if(dis[j] > d+w[i])
                {
                    dis[j] = d+w[i];
                    heap.push({dis[j], j});
                }
            }
        }
    }

    return dis[n];
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);
    }

    int t = dijkstra();
    if(t == -1) printf("-1\n");
    else printf("%d\n", t);

    return 0;
}

Bellman-Ford

AcWing-853 有边数限制的最短路

原题链接

思路

Bellman-Ford算法。由于这里有负权，Dijkstra算法不再适用。这里的注意点请看注释。
复杂度为$O(mn)$。也是迭代n次（这个迭代次数是根据题目限制的最短路中所包含的边的条数），步骤如下：

迭代中先备份边的距离的情况，防止最短路中包含的边数超过限制。
遍历所有边，进行松弛操作（详见代码）

参考代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 510;   
const int maxm = 10010;
const int inf = 0x3f3f3f3f;
int dis[maxn], last[maxn];
struct edge
{
    int a, b, w;
}edges[maxm];
int n, m, k;

int bellman_ford()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;

    for(int i = 0; i < k; i++)  //注意是不超过k条边的最短路，迭代次数不能超过k次
    {
        memcpy(last, dis, sizeof(dis)); //防止最短路距离是最短但边数超过限制的情况
        for(int j = 0; j < m; j++)  //松弛操作
        {
            auto e = edges[j];
            dis[e.b] = min(dis[e.b], last[e.a]+e.w);
        }
    }

    //由于有负权边，可能会出现明明不存在最短路却把dis[n]更新了的情况，而更新后并不等于inf，所以判断条件为大于一个比较大的数（根据题目范围来定）
    if(dis[n] > inf/2) return -1;   
    else return dis[n];
}

int main(void)
{
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        edges[i] = {x, y, z};
    }

    int t = bellman_ford();
    if(t == -1) printf("impossible");
    else printf("%d\n", t);

    return 0;
}

SPFA

AcWing-851 spfa求最短路

原题链接

思路

spfa算法，复杂度为$O(m)$，最坏为$O(nm)$，n为点数，m为边数。求含有负权的最短路，这时候不能用Dijkstra算法。
针对Bellman-Ford算法进行了优化，即只用距离变短了的点去更新其他的点。

参考代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 100010;
const int inf = 0x3f3f3f3f;
int h[maxn], ne[maxn], e[maxn], idx;
int w[maxn], dis[maxn];
bool st[maxn];  //用来保证队列中的元素不重复
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(dis, 0x3f, sizeof(dis));
    dis[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(dis[j] > dis[t] + w[i])
            {
                dis[j] = dis[t] + w[i];
                if(!st[j])  //已经在队列中的点不入队，这里更新了之后由于那个点在队列后面，所以也包括了这里的状态 
                {
                    q.push(j);  //变小了的点才入队，是bellman_ford算法的优化
                    st[j] = true;
                }
            }
        }
    }

    return dis[n];
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);
    }

    int t = spfa();
    if(t == inf) printf("impossible\n");
    else printf("%d\n", spfa());

    return 0;
}

AcWing-852 spfa判断负环

原题链接

思路

判断负环只需要增加一个cnt数组来判断走到当前点走了多少条边，如果从1号点走到n号点走了超过n-1条边，也即大于或等于n条边，那么显然路径中存在环。

参考代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 100010;
const int inf = 0x3f3f3f3f;
int h[maxn], ne[maxn], e[maxn], idx;
int w[maxn], dis[maxn], cnt[maxn];
bool st[maxn];  //用来保证队列中的元素不重复
int n, m;

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

bool spfa()
{
    //由于不需要求最短路，只是判断是否有负环，dis数组初始化为0即可
    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(dis[j] > dis[t] + w[i])
            {
                dis[j] = dis[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);
    }

    bool t = spfa();
    if(t) printf("Yes\n");
    else printf("No\n");

    return 0;
}

Floyd

AcWing-854 Floyd求最短路

原题链接

思路

Floyd算法的应用，用于求多源最短路。思想是动态规划。复杂度为$O(n^3)$。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 210;
const int inf = 0x3f3f3f3f;
int dis[maxn][maxn];
int n, m, k;

void floyd()
{
    //用动态规划的方法去更新dis数组
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = min (dis[i][j], dis[i][k]+dis[k][j]);
}

int main(void)
{
    scanf("%d %d %d", &n, &m, &k);
    //初始化时注意点的编号从1开始
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) dis[i][j] = 0;   //由于不存在负权回路，所以直接把自环都初始化为0即可消去自环
            else dis[i][j] = inf;

    while(m--)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        dis[a][b] = min(dis[a][b], w);  //和前面的初始化搭配，可以消除自环，并且保留重边中的最短边
    }

    floyd();
    while(k--)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        if(dis[x][y] > inf/2) printf("impossible\n");
        else printf("%d\n", dis[x][y]);
    }

    return 0;
}

Prim

AcWing-858 Prim算法求最小生成树

原题链接

思路

Prim算法模板题。Prim算法适用于稠密图，时间复杂度为$O(n^2) $。
它思路和Dijkstra算法类似。步骤如下：

先在不在生成树所属连通块中找距离这个连通块最近的点，找到后将其加入生成树所属连通块（并查集）。
利用这个点更新其他点到这个连通块的距离。

参考代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

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

int prim(void)
{
    memset(dis, 0x3f, sizeof(dis));

    int res = 0;    //存储最小生成树边权重之和
    for(int i = 0; i < n; i++)  
    {
        int t = -1; //类似Dijkstra算法，在没有确定离集合最短距离的点中找距离最短的点
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        st[t] = true;   //找到后将该点加入最小生成树所在的连通块中

        if(i > 0 && dis[t] == inf)  //若不生成树中的第一个点，并且不能和生成树连通，那么就没有最小生成树
            return inf;
        if(i > 0)   //更新生成树中的边权值和
            res += dis[t];

        for(int j = 1; j <= n; j++) //注意这里的更新距离需要放在更新权值和后面，否则会把自环的距离也更新到权值和里面
            dis[j] = min(dis[j], g[j][t]);  //这里与Dijkstra算法不同，dis的意义是该点到集合的距离，所以看该点到已经在集合里的点的最短距离是多少就可以了
    }   

    return res;
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for(int i = 0; i < m; i++)
    {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        g[x][y] = g[y][x] = min(g[x][y], w);    //处理掉重边
    }

    int t = prim();
    if(t == inf) printf("impossible\n");
    else printf("%d\n", t);
    return 0;
}

Kruskal

AcWing-859 Kruskal算法求最小生成树

原题链接

思路

Kruskal算法，适用于稀疏图。复杂度为$O(mlogm)$。
最小生成树概念：
给定一张边带权的无向图 $G=(V,E)$，其中 $V$ 表示图中点的集合 $E$ 表示图中边的集合，$n=|V|$，$m=|E|$。
由 $V$ 中的全部 $n$ 个顶点和 $E$ 中 $n−1$ 条边构成的无向连通子图被称为 $G$ 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 $G$ 的最小生成树。步骤如下：

将所有边按边权升序排序。
遍历所有边，由于是升序排列，如果这条边不在连通块中，则将其加入到连通块。
判断最后若连通块中的边数是否小于n-1，若是，则说明不能形成最小生成树。

参考代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 100010;
const int maxm = 200010;
const int inf = 0x3f3f3f3f;
int p[maxn];
struct Edge
{
    int a, b, w;
}edges[maxm];
int n, m;

bool cmp(Edge x, Edge y)
{
    return x.w < y.w;
}

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

int kruskal(void)
{
    sort(edges, edges + m, cmp);

    //res存储边权和，cnt存储生成树中连通块的边数，若小于n-1，则说明不连通，不能构成生成树
    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;
        int x = find(a), y = find(b);
        if(x != y)
        {
            p[x] = y;   
            res += w;
            cnt++;
        }

        if(i == m - 1 && cnt < n - 1)
            return inf;
    }

    return res;
}

int main(void)
{
    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};
    }
    for(int i = 1; i <= n; i++) //初始化并查集
        p[i] = i;

    int t = kruskal();
    if(t == inf) printf("impossible\n");
    else printf("%d\n", t);

    return 0;
}

染色法判定二分图

AcWing-860 染色法判定二分图

原题链接

思路

染色法判定即可。二分图中不存在奇数环，这也是判断二分图的充要条件。
那么利用染色法，也就是看在遍历所有点的过程中，能否将相邻的点都染成不同的颜色，如果能，则为二分图。
染色过程是用dfs实现的，复杂度为$O(n+m)$，其中n为点数，m为边数。

参考代码

#include <cstdio>
#include <cstring>

const int maxn = 100010;
const int maxm = 200010;
int h[maxn], ne[maxm], e[maxm], idx;
int color[maxn];
int n, m;

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;   //记录下当前dfs起点的颜色
    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] == color[u])   //相邻结点颜色相同，发生矛盾，这里也处理了自环的情况
            return false;
    }

    return true;    //如果所有点都顺利染色，则该图是二分图
}

int main(void)
{
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }

    bool flag = true;   //标记染色过程中是否出现矛盾
    //下面必须写成循环，不能直接dfs(1,1)，因为图不一定连通
    for(int i = 1; i <= n; i++)
    {
        if(!color[i])
        {
            if(!dfs(i, 1))  //深搜起点统一染成1号颜色
            {
                flag = false;
                break;
            }
        }
    }

    if(flag) printf("Yes\n");
    else printf("No\n");

    return 0;
}

匈牙利算法

AcWing-861 二分图的最大匹配

原题链接

思路

匈牙利算法。将二分图分成两半来看，我们不妨遍历左半结点，去检查是否能在右半结点中找到能够与之匹配的点。思路详见代码。
该算法的时间复杂度为$O(nm)$，n为点数，m为边数。这里的时间复杂度只是理论上的，实际的运行时间一般来说是远小于这个复杂度的。

参考代码

#include <cstdio>
#include <cstring>

const int maxn = 510;
const int maxm = 100010;
int h[maxn], e[maxm], ne[maxm], idx;
int match[maxn];    //标记当前结点是否已经匹配并存储与之匹配的结点
bool st[maxn];  //标记当前结点在二分图中另一半的结点是否已被遍历
int n1, n2, m;

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(void)
{
    scanf("%d %d %d", &n1, &n2, &m);
    memset(h, -1, sizeof(h));
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    int res = 0;    //存储匹配成功的数量
    for(int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof(st));
        if(find(i)) res++;
    }
    printf("%d\n", res);

    return 0;
}

目录

Acwing算法基础课第三讲总结

本章思维导图

DFS（深度优先搜索）

AcWing-842 排列数字

AcWing-843 n-皇后问题

BFS（广度优先搜索）

AcWing-844 走迷宫

AcWing-845 八数码

树与图的深度优先遍历

AcWing-846 树的重心

树与图的广度优先遍历

AcWing-847 图中点的层次

拓扑排序

AcWing-848 有向图的拓扑序列

Dijkstra

AcWing-849 Dijkstra求最短路Ⅰ

AcWing-850 Dijkstra求最短路Ⅱ

Bellman-Ford

AcWing-853 有边数限制的最短路

SPFA

AcWing-851 spfa求最短路

AcWing-852 spfa判断负环

Floyd

AcWing-854 Floyd求最短路

Prim

AcWing-858 Prim算法求最小生成树

Kruskal

AcWing-859 Kruskal算法求最小生成树

染色法判定二分图

AcWing-860 染色法判定二分图

匈牙利算法

AcWing-861 二分图的最大匹配