logo
shylove
banner
NEWS LETTER

算法基础课-搜索与图论

Scroll down

DFS

排列问题

#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯，取出 i 回溯是关键
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
}

n皇后问题

//cpp
#include <iostream>
using namespace std;

const int N = 11;

char q[N][N];//存储棋盘
bool dg[N * 2], udg[N * 2], cor[N];//点对应的两个斜线以及列上是否有皇后

int n;

void dfs(int r)
{
    if(r == n)//放满了棋盘，输出棋盘
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                cout << q[i][j];
            cout << endl;
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < n; i++)//第 r 行，第 i 列 是否放皇后
    {
        if(!cor[i] && !dg[i + r] && !udg[n - i + r])//不冲突，放皇后 
        //为什么这里能判断，因为同一条斜线上i + j 和 i - j 相等，所以可以这样处理
        {
            q[r][i] = 'Q';
            cor[i] = dg[i + r] = udg[n - i + r] = 1;//对应的 列， 斜线 状态改变
            dfs(r + 1);//处理下一行
            cor[i] = dg[i + r] = udg[n - i + r] = 0;//恢复现场,为什么要恢复现场，准备下一种情况的输入递归
            q[r][i] = '.';
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            q[i][j] = '.';
    dfs(0);
    return 0;
}

BFS

走迷宫问题

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;

//有没有明白的点可以看这个链接https://www.acwing.com/solution/content/36520/
const int N = 110;
int g[N][N];//存储地图
int f[N][N];//存储距离
int n, m;
void bfs(int a, int b)//广度优先遍历
{
    queue<PII> q;
    q.push({a, b});//入队
    //初始点的距离为 0.
    //可以不要这一句，因为f初始化的时候，各个点为0
    f[0][0] = 0;
    while(!q.empty())
    {
        PII start = q.front();//将队列的第一个元素赋值给start元素
        q.pop();//将队首元素移出,这样的操作通常用于处理当前层次的节点
        //这一句可以不要，因为入队的时候就置为了1
        g[start.first][start.second] = 1; //是标记当前处理的点 (start.first, start.second) 已经被访问过，避免重复访问
        int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
        for(int i = 0; i < 4; i++)//往四个方向走
        {
            //当前点能走到的点
            int x = start.first + dx[i], y = start.second + dy[i]; //仔细琢磨这个地方，就可以知道它表示四个移动方向了
            //如果还没有走过
            if(g[x][y] == 0) //确定是可以走的
            {
                //走到这个点，并计算距离
                g[x][y] = 1;//标记为已经访问
                f[x][y] = f[start.first][start.second] + 1;//从当前点走过去，则距离等于当前点的距离+1.
                //这个点放入队列，用来走到和它相邻的点。
                q.push({x, y});//将他入队
            }

        }
    }
    cout << f[n][m];//但是 BFS 本身的性质保证了在搜索过程中首次到达每个点的路径一定是最短路径
}

int main()
{
    memset(g, 1, sizeof(g)); //memset函数，将所有的数组中的元素设置为特定值
    cin >> n >>m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
        }
    }
    bfs(1,1);

}

八数码问题

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


//不明白可以看这个链接https://www.acwing.com/solution/content/36346/
using namespace std;
// 保存各个序列
queue<string> q;
string s;
// 保存序列与对应的交换次数
unordered_map<string, int> h;

int main()
{
    // 输入原始序列
    for(int i = 1; i <= 9; i++)
    {
        char c;
        cin >> c;
        s += c;
    }
    // 保存初始状态
    h[s] = 0;
    q.push(s);
    // 定义上下左右四个交换方向
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    // 依次进行交换
    while(!q.empty())
    {
        // 获得当前序列
        string t = q.front();
        q.pop();
        // 如果是最后结果，输出答案
        if(t == "12345678x")
        {
            cout << h[t] << endl;
            return 0;
        }
        // 找到 x 的位置
        int pos = t.find('x');
        // 计算 x 的坐标
        int a = pos /3 , b = pos % 3 ;
        // 获取当前序列对应的交换次数
        int dist = h[t];

        // 尝试和四个方向的元素进行交换
        for(int i = 0; i < 4; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            // 判断是否越界
            if(x >= 0 && x <= 2 && y >= 0 && y <= 2)
            {
                // 交换
                swap(t[pos], t[3 * x + y]);//这里这个t[3*x+y]是指的在一维中的索引位置
                // 如果是个新序列，就保存新序列和对应的交换次数
                if(h.find(t) == h.end())
                {
                    h[t] = dist + 1;
                    q.push(t);
                }
                // 恢复现场，进行下一个方向的交换
                swap(t[pos], t[3 * x + y]);//交换只是交换位置
            }
        }
    }
    // 没有得到结果序列，输出-1
    cout << -1;
    return 0;
}

树和图的深度优先遍历

树的重心问题


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

using namespace std;

//这个题目的代码我真的很迷，看了一个多小时都有点摸不着头脑

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目

bool st[N]; //记录节点是否被访问过，访问过则标记为true

//a所对应的单链表中插入b  a作为根 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// dfs 框架
/*
void dfs(int u){
    st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) {
            dfs(j);
        }
    }
}
*/

//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树的节点数
        }
    }

    //n-sum 如图中的n-size值，不包括根节点4；
    res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的节点数
    return sum;
}

int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin >> n; //表示树的结点数

    // 题目接下来会输入，n-1行数据，
    // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }

    dfs(1); //可以任意选定一个节点开始 u<=n

    cout << ans << endl;//最后是输出ans我终于悟了

    return 0;
}

/*
它这里实际上没有删除这个概念，它就只是，找到树中的一个节点，把它一分为二，位于它下面的，和除了“从此点蔓延下去的树（包括此点）”之外的所有节点，对于它下面的这类，处理是用一个for循环遍历和此点的所有出度，找到其中节点数，也就是联通量最大的一颗子树，记录下来，然后用这颗树总的节点数减去这颗最大的子树节点，再减一，也就是减去当前的节点，得到的值就是除了“从此点蔓延下去的树（包括此点）”之外的所有节点，取个min，就是答案了，每一个点一分为二后的最优解都会存到全局变量里，也就是每一次的dfs执行，都会将当前这个点的最大联通量与全局最优联通量比较，自然执行完所有dfs，此时的全局变量就是我们的答案。
说起来有点绕，其实要想明白它每一次往下递归调用dfs，不仅仅是在算子树的节点大小，同时也在并行处理当前被dfs的这个节点它的最优解，就行了,最后输出的是ans
*/

树和图的广度优先遍历

图中点的层次


//简单的广度优先遍历问题
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 100010;

int h[N],ne[N], e[N], idx;//邻接表数据结构
int dist[N];//存储距离
int st[N];//标记点是否走到过
int n, m;

void add(int a, int b)//邻接表存储图
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs()
{
    memset(dist, 0x3f, sizeof(dist));//初始都没有走到过，距离无穷大
    dist[1] = 0;//从1号节点开始，距离为0
    queue<int> q;//队列
    q.push(1);//1号节点入队列
    st[1] = 1;//1到1的距离为0，已经求出
    while(q.size())//对列非空，就一直往后搜索
    {
        int t = q.front();//队头出队，找该点能到的点
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点，i为节点索引
        {
            int j = e[i];//通过索引i得到t能到的节点编号
            if(!st[j])//如果没有遍历过
            {
                dist[j] = dist[t] + 1;//距离为t号节点的距离+1
                q.push(j);//节点入队
                st[j] = 1;//入队后标记，已经遍历过了
            }
        }
    }
}

int main()
{
    cin >> n >>m;
    memset(h, -1, sizeof h);//初始化，所有节点没有后继，后继都是-1
    for(int i = 0; i < m; i++)//读入所有边
    {
        int a, b;
        cin >> a >> b;
        add(a, b);//加入邻接表
    }
    bfs();//广度优先遍历

    cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);//如果到n号节点的距离不是无穷大，输出距离，如果是无穷大，输出-1.
    return 0;
}

拓扑排序

有向图的拓扑序列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
//有疑问看这个链接：https://www.acwing.com/solution/content/103954/
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int q[N], hh = 0, tt = -1;//队列保存入度为0的点，也就是能够输出的点，
int n, m;//保存图的点数和边数
int d[N];////保存各个点的入度

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

void topsort(){
    for(int i = 1; i <= n; i++){//遍历一遍顶点的入度。
        if(d[i] == 0)//如果入度为 0, 则可以入队列
            q[++tt] = i;
    }
    while(tt >= hh){//循环处理队列中点的
        int a = q[hh++];
        for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边
            int b = e[i];//a 有一条边指向b
            d[b]--;//删除边后，b的入度减1
            if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出，入队列
                q[++tt] = b;
        }
    }
    if(tt == n - 1){//如果队列中的点的个数与图中点的个数相同，则可以进行拓扑排序
        for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点，依次输出
            cout << q[i] << " ";
        }
    }
    else//如果队列中的点的个数与图中点的个数不相同，则可以进行拓扑排序
        cout << -1;//输出-1，代表错误
}


int main(){
    cin >> n >> m;//保存点的个数和边的个数
    memset(h, -1, sizeof h);//初始化邻接矩阵
    while (m -- ){//依次读入边
        int a, b;
        cin >> a >> b;
        d[b]++;//顶点b的入度+1
        add(a, b);//添加到邻接矩阵
    }
    topsort();//进行拓扑排序
    return 0;
}

Dijstra

Dijstra求最短路径I

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

const int N = 510, M = 100010;

int h[N], e[M], ne[M], w[M], idx;//邻接表存储图
int state[N];//state 记录是否找到了源点到该节点的最短距离
int dist[N];//dist 数组保存源点到其余各个节点的距离
int n, m;//图的节点个数和边数

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

void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));//dist 数组的各个元素为无穷大
    dist[1] = 0;//源点到源点的距离为置为 0
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)//遍历 dist 数组，找到没有确定最短路径的节点中距离源点最近的点t
        {
            if (!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        state[t] = 1;//state[i] 置为 1。

        for (int j = h[t]; j != -1; j = ne[j])//遍历 t 所有可以到达的节点 i
        {
            int i = e[j];
            dist[i] = min(dist[i], dist[t] + w[j]);//更新 dist[j]
        }


    }
}

int main()
{
    memset(h, -1, sizeof(h));//邻接表初始化

    cin >> n >> m;
    while (m--)//读入 m 条边
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }

    Dijkstra();
    if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了，则存在路径
        cout << dist[n];
    else
        cout << "-1";
}

Dijstra求最短路径II



//利用小根堆寻找最短距离点
//priority_queue：是C++标准库中的优先队列类模板，实现了一个堆（heap）数据结构。
//更多详细的解释可以看这个链接：https://www.acwing.com/solution/content/38318/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的头文件

using namespace std;

typedef pair<int, int> PII;//堆里存储距离和节点编号

const int N = 1e6 + 10;

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 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, distance = t.first;//ver:节点编号，distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定，则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], 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;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

bellman-ford

有边数限制的最短路

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环 ，每一次循环都遍历所有的边
        memcpy(back, dist, sizeof dist);//的memcpy函数，其目的是将存储在dist数组中的数据复制到back数组中。具体而言，memcpy用于在内存之间复制一定数量的字节。在这里，back是目标数组，dist是源数组，sizeof dist表示要复制的字节数，即dist数组的大小。
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else 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);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");
    else cout << res;

    return 0;
}

spfa

spfa求最短路

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

//和bellman-ford区别就在于，它更新最短路径时，没有纯暴力，采取了如果有变化就加入队列的方式

const int N = 100010;
int h[N], e[N], w[N], ne[N], idx;//邻接表，存储图
int st[N];//标记顶点是不是在队列中
int dist[N];//保存最短路径的值
int q[N], hh, tt = -1;//队列

void add(int a, int b, int c){//图中添加边和边的端点
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa(){
    q[++tt] = 1;//从1号顶点开始松弛，1号顶点入队
    dist[1] = 0;//1号到1号的距离为 0
    st[1] = 1;//1号顶点在队列中
    while(tt >= hh){//不断进行松弛
        int a = q[hh++];//取对头记作a，进行松弛
        st[a] = 0;//取完队头后，a不在队列中了
        for(int i = h[a]; i != -1; i = ne[i])//遍历所有和a相连的点
        {
            int b = e[i], c = w[i];//获得和a相连的点和边
            if(dist[b] > dist[a] + c){//如果可以距离变得更短，则更新距离

                dist[b] = dist[a] + c;//更新距离

                if(!st[b]){//如果没在队列中
                    q[++tt] = b;//入队
                    st[b] = 1;//打标记
                }
            }
        }
    }
}
int main(){
    memset(h, -1, sizeof h);//初始化邻接表
    memset(dist, 0x3f, sizeof dist);//初始化距离
    int n, m;//保存点的数量和边的数量
    cin >> n >> m;
    for(int i = 0; i < m; i++){//读入每条边和边的端点
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);//加入到邻接表
    }
    spfa();
    if(dist[n] == 0x3f3f3f3f )//如果到n点的距离是无穷，则不能到达 
        cout << "impossible";
    else cout << dist[n];//否则能到达，输出距离
    return 0;
}

spfa求负环

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

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[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 ++ ;
}

bool 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; //如果路径的长度大于等于n，就说明存在负环
                if (!st[j])
                {
                    q.push(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;
}

Floyd

Floyd求最短路

#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
int d[N][N];


//floyd算法很简单，思路在胡凡算法笔记的398页解释的非常透彻且详细

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 >> 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;
    while(m--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        //注意保存最小的边
    }
    floyd();
    while(k--) {
        cin >> x >> y;
        if(d[x][y] > INF/2) puts("impossible");
        //由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}

Prim

Prim算法求最小生成树

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

const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

void prim()
{
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }

        //2022.6.1 发现测试用例加强后，需要判断孤立点了
        //如果孤立点，直返输出不能，然后退出
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }


        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }

    cout << res;

}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    prim();//求最下生成树
    //getPath();//输出路径
    return 0;
}

Kruskal

算法求最小生成树

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

using namespace std;
const int N = 100010;
int p[N];//保存并查集

//并查集判断是否构成回路

struct E{
    int a;
    int b;
    int w;
    bool operator < (const E& rhs){//通过边长进行排序
        return this->w < rhs.w;
    }

}edg[N * 2];
int res = 0;

int n, m;
int cnt = 0;
int find(int a){//并查集找祖宗
    if(p[a] != a) p[a] = find(p[a]);
    return p[a];
}
void klskr(){
    for(int i = 1; i <= m; i++)//依次尝试加入每条边
    {
        int pa = find(edg[i].a);// a 点所在的集合
        int pb = find(edg[i].b);// b 点所在的集合
        if(pa != pb){//如果 a b 不在一个集合中
            res += edg[i].w;//a b 之间这条边要
            p[pa] = pb;// 合并a b
            cnt ++; // 保留的边数量+1
        }
    }
}
int main()
{

    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;//初始化并查集
    for(int i = 1; i <= m; i++){//读入每条边
        int a, b , c;
        cin >> a >> b >>c;
        edg[i] = {a, b, c};
    }
    sort(edg + 1, edg + m + 1);//按边长排序
    klskr();
    //如果保留的边小于点数-1，则不能连通
    if(cnt < n - 1) {
        cout<< "impossible";
        return 0;
    }
    cout << res;
    return 0;
}

染色法判定二分图

染色法判定二分图

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

using namespace std;

const int N = 100010 * 2;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int color[N];//保存各个点的颜色，0 未染色，1 是红色，2 是黑色
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;//u的点成 c 染色

    //遍历和 u 相邻的点
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int b = e[i];                   
        if(!color[b])//相邻的点没有颜色,则递归处理这个相邻点
        {
            if(!dfs(b, 3 - c)) return false;//（3 - 1 = 2， 如果 u 的颜色是2，则和 u 相邻的染成 1）
                                            //（3 - 2 = 1， 如果 u 的颜色是1，则和 u 相邻的染成 2）
        }
        else if(color[b] && color[b] != 3 - c)//如果已经染色，判断颜色是否为 3 - c
        {                                     
            return false;//如果不是，说明冲突，返回                   
        }
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表
    cin >> n >> m;
    for(int i = 1; i <= m; i++)//读入边
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    for(int i = 1; i <= n; i++)//遍历点
    {
        if(!color[i])//如果没染色
        {
            if(!dfs(i, 1))//染色该点，并递归处理和它相邻的点
            {
                cout << "No" << endl;//出现矛盾，输出NO 
                return 0;
            }

        }
    }
    cout << "Yes" << endl;//全部染色完成，没有矛盾，输出YES
    return 0;
}

匈牙利算法

二分图的最大匹配

#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
// 邻接表存储图
int n1, n2, m;
int h[500], e[100010],ne[100010], idx = 0;
//st 标记是否递归找过， match[x]：和 x 编号的男生的编号
int st[510], match[510];
//存图函数
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a]; h[a] = idx++;
}
//递归找可以匹配的点

//详细得思路主要是这个链接：https://www.acwing.com/solution/content/179030/
bool find(int x){
    // 和各个点尝试能否匹配
    for(int i = h[x]; i != -1; i = ne[i]){
        int b = e[i];
        if(!st[b]){//打标记
            st[b] = 1;
            // 当前尝试点没有被匹配或者和当前尝试点匹配的那个点可以换另一个匹配
            if(match[b] == 0 || find(match[b])){//注意这里find(match[b]是寻找下一个匹配的女生
                // 和当前尝试点匹配在一起
                match[b] = x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n1 >> n2 >> m;
    // 保存图，因为只从一遍找另一边，所以该无向图只需要存储一个方向
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    //为各个点找匹配
    for(int i = 1; i <= n1; i++){
        memset(st, 0, sizeof st);
        //找到匹配
        if(find(i)) res++;
    }
    cout << res;
    return 0;
}
其他文章
26
2024/01
日记
最近
  • 24/01/26
  • 21:14
  • 501
  • 1
© 2023- 2024 shylove
"星余" 再次运行已经 天