DFS

数字排列：

#include<iostream>

using namespace std;

const int N = 1000;
int path[N];  //保存路径的现状
bool st[N];  //保存节点是否被用过，true为用过
int n;

void dfs(int u)
{
    if (u == n)  //走到尽头
    {
        for (int i = 0; i < n; i++)
        {
            cout << path[i] << " ";
        }
        puts("");  //换行
        return;
    }

    for (int i = 1; i <= n; i++)  //从1开始遍历是因为第0层只有一种可能，即三个位置全空
    {
        if (st[i] == false)
        {
            path[u] = i;  //表示第u个空位已经被i占据
            st[i] = true;
            dfs(u + 1);  //往下走
            st[i] = false;  //回溯时恢复原状
        }
    }
}

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

    return 0;
}

N皇后

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100;
char g[N][N];
bool col[N];  //列
bool dg[N];  //对角线
bool udg[N];  //反对角线
int n;

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i++)
            cout << g[i] << " ";
        cout << endl;
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (col[i] == false && dg[n - u + i] == false && udg[u + i] == false)  //三种情况都没有被放过
        {
            g[u][i] = 'Q';  //该位置直接放皇后
            col[i] = dg[n - u + i] = udg[u + i] = true;  //三种情况直接被使用
            dfs(u + 1);  //往下走
            col[i] = dg[i] = udg[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] = '.';  //'.'表示空地， Q表示皇后

    dfs(0);

    return 0;
}

BFS

走迷宫

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N];  //存图， 0表示可以走，1表示不能走
int d[N][N];  //-1表示没用过, 0表示用过
queue<PII> q;

int bfs()
{
    q.push({ 0, 0 });
    memset(d, -1, sizeof d);
    d[0][0] = 0; //初始位置一定用过
    int dy[4] = { 0, 1, 0, -1 };  //上下左右四个方向
    int dx[4] = { -1, 0, 1, 0 };


    while (!q.empty())  //队列非空
    {
        PII t = q.front();  // t == 队头
        q.pop();  //队头出队

        for (int i = 0; i < 4; i++)  //枚举四个方向
        {
            int x = t.first + dx[i]; //x表示沿着此方向会走到哪一点
            int 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];
}

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

树的重心

dfs

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1000;
const int M = 10000;
int h[N], e[M], ne[M], idx;
int n, 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;  //sum表示当前子树的节点数量，res表示将u点去除后，剩下的子树中节点数量的最大值

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j] == false)
        {
            int s = dfs(j);
            res = max(res, s);  //记录最大联通子图的节点数
            sum += res;  //以j为根的树 的节点数
        }
    }
    res = max(res, n - sum);  //选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans);

    return sum;
}

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

    dfs(1);

    cout << ans << endl;

    return 0;
}

图中点的层次

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1000;
int h[N], e[N], ne[N], idx;
int d[N];  //存距离，-1表示没拓展过
int n, m;
queue<int> q;

void add(int a, int b)  //建立边函数
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

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

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

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];  //j等于当前遍历的点的值
            if (d[j] == -1)  //j没被拓展过
            {
                d[j] = d[t] + 1;  //拓展j
                q.push(j);
            }
        }
    }

    return d[n];
}

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

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

有向图的拓扑排序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1000;
int h[N], e[N], ne[N], idx;
int d[N], top[N], cnt;  //入度，top是拓扑排序的序列,cnt是top的元素个数
int n, m;

void add(int a, int b)  //建立边函数
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool topsort()
{
    queue<int> q;

    for (int i = 1; i <= n; i++)
        if (d[i] == 0)
            q.push(i);  //所有入度为0的点全部入队

    while (!q.empty())
    {
        int t = q.front();
        top[cnt++] = t;
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j]--;  //删除边
            if (d[j] == 0)  //入度删除到0代表已经排好序
                q.push(j);  //入队
        }

    }

    if (cnt < n - 1)
        return false;
    else
        return true;
}

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() == 0)
        cout << "-1" << endl;
    else
    {
        for (int i = 0; i < n; i++)
            cout << top[i] << " ";
        cout << endl;
    }

    return 0;
}

bellman_ford算法

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;  //N点数，M边数
int dist[N], backup[N]; //backup[]是dist的备份
int n, m, k;

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++)  //循环k次（两点路径不超过k条边）
    {
        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);  //注意是backup[a]
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2)  //因为存在负权边
        return -1;

    return dist[n];
}

int main()
{
    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)
        cout << "impossible" << endl;
    else
        cout << t << endl;

    return 0;
}

spfa

#include<iostream>
#include<cstring>
#include<algorithm>
#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 s[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);  //起点入队
    s[1] = true;

    while (q.size())  //队列非空
    {
        int t = q.front();
        q.pop();

        s[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])  //更新t的所有出边
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (s[j] ==  false)  //没走过且变小(变小是上面一个if)
                {
                    q.push(j);
                    s[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f)
        return -1;
    else
        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)
        cout << "impossible" << endl;
    else
        cout << t << endl;

    return 0;
}

floyd

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, INF = 1e9;  // INF正无穷

int n, m, q;  //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);  //取最小值，去掉重边
    }

    while (q--)  //询问操作
    {
        int a, b;
        cin >> a >> b;

        if (d[a][b] > INF / 2)
            cout << "impossible" << endl;
        else
            cout << d[a][b] << endl;
    }

    return 0;
}

最小生成树

prim算法

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;  // N是点数，INF正无穷
int n, m;     //点和边
int g[N][N];  //存图
int dist[N];  //存距离
bool s[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++)  //令 t = 找到集合s外离集合s最近的点
            if (s[j] == false && (t == -1 || dist[t] > dist[j])) //j不在集合里面且（t没走过或者t的距离大于j）  注意：s[j]不是s[t]
                t = j;

        s[t] = true;  //标志t走过

        if (i != 0 && dist[t] == INF)  //判断是否连通，有无最小生成树, i == 0时只有一个点，没有树生成，要特判
            return INF;

        if (i != 0)
            res += dist[t];  //每找到一个点加入集合s，更新总距离

        for (int j = 1; j <= n; j++)  //用t更新其他点到集合s的距离
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> 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 ans = prim();
    if (ans == INF)
        cout << "impossible" << endl;
    else
        cout << ans << endl;

    return 0;
}

kruskal算法（克鲁斯卡尔算法）

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 200010;
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()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++)  //输入边及权重
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = { a, b, w };
    }

    for (int i = 1; i <= n; i++)  //并查集初始化
        p[i] = i;

    int res = 0, cnt = 0;  //res是最小生成树里面的权重之和，cnt是边的数量

    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);  //并查集模板，找到a b的祖宗节点
        if (a != b)  //a b不连通
        {
            p[a] = b;   //如果a b不连通，则将这条边加入集合
            res += w;
            cnt++;
        }
    }

    if (cnt < n - 1)
        cout << "impossible" << endl;
    else
        cout << res << endl;

    return 0;
}

染色法判断二分图

#include<iostream>
#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];  //监测是否被染过以及是1号色还是2号色

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

bool dfs(int u, int c)  //c号色
{
    color[u] = c;  //先将u染色

    for (int i = h[u]; i != -1; i = ne[i])  //遍历和u连通的所有点
    {
        int j = e[i];
        if (color[j] == 0)  //如果j没被染过色
        {
            if (dfs(j, 3 - c) == false)  //则染成另外一种颜色，1号色则变成2号色，2号色变成1号色（3 - c）
                return false;
        }
        else if (color[j] == c)  //颜色冲突
            return 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;  //标记符号，true表示染色没有矛盾
    for (int i = 1; i <= n; i++)
        if (color[i] == 0)  //没有被染过色
            if (dfs(i, 1) == false)  //染色有矛盾，直接停止
            {
                flag = false;
                break;
            }

    if (flag == true)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

匈牙利算法求最大匹配

#include<iostream>
#include<cstring>

using namespace std;

const int N = 520, M = 100010;
int n1, n2, m;  //左半边点数，右半边点数，边数
int h[N], e[M], ne[M], idx;
int match[N];  //存匹配对象，0表示没有匹配
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] == false)  //j没有被匹配成功
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))  //j没有匹配过，或者可以为已经匹配的左边点找到另一个下家
            {
                match[j] = x;
                return true;
            }

        }

    }

    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;

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

    int res = 0;  //配对数
    for (int i = 1; i <= n1; i++)  //遍历左半边，找到关系
    {
        memset(st, false, sizeof st);
        if (find(i))
            res++;
    }

    cout << res << endl;

    return 0;
}