二刷算法基础课(图论)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

二刷算法基础课(图论)

作者：

SQlay , 2024-11-20 23:26:23 , 所有人可见 , 阅读 4

multiset存放具体方案,用for输出

acwing842：dfs:递归

#include <bits/stdc++.h>

using namespace std;

const int N = 10 ;

int n ;
multiset<vector<int> > res;
vector<int> path;
bool st[N];


void dfs(int u)
{
    if (u > n) //u == n 时 第n个位置还未填
    {
        res.insert(path);
        return;
    }
    for (int i = 1 ; i <= n ; i ++)
    {
        if (!st[i])
        {   
            st[i] = true;
            path.push_back(i); 
            dfs(u + 1);
            st[i] = false;
            path.pop_back();
        }
    }

}

int main()
{
    cin >> n ;
    dfs(1);
    for (auto vec : res )
    {
        for (auto x : vec )
            cout << x << ' ' ;
        cout << endl ;
    }

    return 0;

}

acwing844:bfs：队列

#include <bits/stdc++.h>

using namespace std;

typedef pair<int , int > PII ;

const int N = 110 , M = 110 ;

int g[N][M];
int n , m ;
PII d[4] = {{1,0} , {0,1} , {-1,0} , {0,-1}};
int dist[N][M] ;

void bfs()
{
    memset(dist , -1 , sizeof dist);
    dist[1][1] = 0;

    queue<PII > q;
    q.push({1,1});

    while (q.size())//
    {
        auto t = q.front();
        q.pop();
        int x = t.first , y = t.second ;

        for (int k = 0 ; k < 4 ; k ++)
        {
            int dx = d[k].first , dy = d[k].second;
            int i = x + dx , j = y + dy;
            if (i >= 1 && i <= n && j >= 1 && j <= m && dist[i][j] == -1 && g[i][j] == 0)
            {
                q.push({i,j});         
                dist[i][j] = dist[x][y] + 1;
            }
        } 
    }

}

int main()
{
    cin >> n >> m ;

    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
            cin >> g[i][j];
    bfs();
    cout << dist[n][m] << endl;
    return 0 ;
}

最短路径：若权值相等可以用bfs求最短路；权值不等用dijkstra、bellman-ford、spfa、floyd，其中dijkstra不能处理负边，floyd不能处理负环

acwing847 : bfs(权值相等)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

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

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

void bfs()
{
    memset(dist , -1 ,sizeof dist);//
    dist[1] = 0;

    queue<int > q;
    q.push(1);

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

        st[t] = true;

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

}

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

    bfs();

    cout << dist[n] << endl ;

    return 0 ;
}

acwing847: dijkstra//需要注意堆优化使用到的优先队列默认是大根堆，需要再改成小根堆。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int , int> PII;

const int N = 1e5+10;

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

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

void dijkstra()
{
    memset(dist , 0x3f ,sizeof dist);//
    dist[1] = 0;

    priority_queue<PII , vector<PII > , greater<PII> > q; 
    q.push({0 , 1});

    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int i = t.second , d = t.first;

        if (st[i]) continue; //这一步y总说是减少冗余，是因为本题有重边吗。如果是简单图直接st[i] = true就可以。
        else st[i] = true;

        for (int u = h[i] ; u != -1 ; u = ne[u])
        {
            int j = e[u];
            if (dist[j] > d + 1)
            {
                dist[j] = d + 1;
                q.push({dist[j] , j});
            }
        }
    }

}

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

    dijkstra();

    if (dist[n] != 0x3f3f3f3f) cout << dist[n] << endl ;
    else puts("-1");

    return 0 ;
}

acwing853: bellman_ford(可以用来判断有没有负环(但这个负环得能从1这个起点走到)，但不能解决负环，每次松弛操作时使用的是上一次的dist数组(backup数组)，为了避免发生串联 )

#include <bits/stdc++.h>

using namespace std;

const int N = 510 , M = 10010;

int n , m , k ;
int dist[N] , backup[N];

struct Edge
{
    int a , b , w ;

}edge[M];

void bellman_ford()
{
    memset(dist , 0x3f , 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 = edge[j].a , b = edge[j].b , w = edge[j].w;
            dist[b] = min(dist[b] , backup[a] + w); //backup[a] + w ;
        }
    }
}

int main()
{
    cin >> n >> m >> k ;

    for (int i = 0 ; i < m ; i ++)  cin >> edge[i].a >> edge[i].b >> edge[i].w ;

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n] << endl;

    return 0 ;
}

spfa(只要一个点的dist被更新就用该点去检查是否能更新别的边)(可以判断是否存在负环)

与bellman_ford相比：spfa只用更新过dist的点去更新其他点，而bellman_ford每次都会遍历所有边.

与dijkstra堆优化，bfs(都用到队列)相比：dijkstra每次用dist最短的点去更新别的点，而spfa则是每次用队头(被更新过的点，但不一定dist最短)，spfa更类似于优化bfs只能求权值相等的最短路的缺点.

acwing851：spfa求最短路

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

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

void 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;
        //用t更新所有邻边
        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];//更新j
                if (!st[j])//如果j不在队中，将该点加入队中
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;

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

    spfa();

    if (dist[n] == 0x3f3f3f3f) puts("impossible");
    else cout << dist[n] << endl;

    return 0 ;
}

acwing852 : spfa判负环

#include <bits/stdc++.h>

using namespace std;

const int N = 2010 , M = 10010;

int e[M] , ne[M] , h[N] , w[M] , idx ;
int n , m ;
int dist[N] , cnt[N];
bool st[N];

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

bool spfa()
{
    memset(dist , 0x3f , sizeof dist);
    dist[1] = 0 ;

    queue<int > q ;
    //所有点入队，因为1不一定能到负环
    for (int i = 1 ; i <= n ; i ++)
    {
        q.push(i);
        st[i] = 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])//w[i] , i是地址
            {
                dist[j] = dist[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()
{
    cin >> n >> m ;

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

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}

acwing848 : 拓扑排序

bfs

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int e[N] , h[N] , ne[N] , idx , d[N] ;
int n , m ;
vector<int > res;

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

bool bfs()
{
    queue<int > q;

    for (int i = 1 ; i <= n ; i ++) 
        if (d[i] == 0)
        {
            q.push(i);
        }

    while (q.size())
    {
        auto t = q.front();
        res.push_back(t);
        q.pop();

        for (int i = h[t] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            d[j] --;

            if (d[j] == 0)
            q.push(j);
        }
    }

    if (res.size() == n) return true;
    else return false;
}

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

    if (bfs())
    {
        for (auto x : res) cout << x << ' ' ;
    }
    else puts("-1");

    return 0;
}

dfs

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int n , m ;
stack<int > s;
vector<int > res;
int st[N];
struct Node
{
    int val;
    Node *next ;

    Node(int _val) : val(_val) , next(NULL) {}
}*head[N];

void add(int a , int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p ;
}

bool dfs(int u)
{
    st[u] = 1;

    for (auto i = head[u] ; i ; i = i->next)
    {
        int j = i->val;

        if (st[j] == 1) return false;
        else if (!st[j])
        {
            if (!dfs(j)) return false;
        }
    }

    st[u] = 2;
    res.push_back(u);//保存的是逆拓扑序列
    return true;
}

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

    for (int i = 1 ; i <= n ; i ++)
    {
        if (!st[i] && !dfs(i)) 
        {
            puts("-1");
            return 0;
        }
    }

    reverse(res.begin() , res.end());
    for (auto x : res) cout << x << ' ' ;

    return 0 ;
}

acwing854 : floyd(求多源最短路，不能解决负环图)

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int g[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 ++)
                g[i][j] = min(g[i][j] , g[i][k] + g[k][j]); 
}

int main()
{
    cin >> n >> m >> k ;

    memset(g , 0x3f , sizeof g);
    for (int i = 1 ; i <= n ; i ++) g[i][i] = 0;//初始化

    for (int i = 0 ; i < m ; i ++)
    {
        int x , y , w; 
        cin >> x >> y >> w;
        g[x][y] = min(g[x][y] , w);
    }

    floyd();

    while (k --)
    {
        int x , y ;
        cin >> x >> y ;
        if (g[x][y] > 0x3f3f3f3f / 2) puts("impossible");
        else cout << g[x][y] << endl ;
    }
    return 0 ;
}

acwing858 : Prim(每次选距离集合最近的点(且不在集合内)，用这个点去更新集合外的点距离集合的距离)

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int g[N][N];
int n , m ;
int dist[N];
bool st[N];

int Prim()
{
    int res = 0 ;
    memset(dist , 0x3f , sizeof dist);

    for (int i = 0 ; i < n ; i ++)
    {
        int t = -1 ;

        for (int j = 1 ; j <= n ; j ++)
        {
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
            t = j ;
        }

        if (i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f ;//i 如果不是第一次取点
        if (i == 0) dist[t] = 0 ;//起点

        for (int j = 1 ; j <= n ; j ++)
        {
            if (j != t)
            dist[j] = min(dist[j] , g[t][j]);
        }

        res += dist[t];
        st[t] = true;
    }

     return res ;
}

int main()
{
    cin >> n >> m ;
    //初始化
    memset(g , 0x3f , sizeof g);
    for (int i = 1 ; i <= n ; i ++) g[i][i] = 0 ;

    for (int i = 0 ; i < m ; i ++)
    {
        int x , y , w;
        cin >> x >> y >> w;
        g[x][y] = g[y][x] = min(g[x][y] , w);
    }

    int res = Prim();

    if (res == 0x3f3f3f3f) puts("impossible");
    else cout << res << endl;

    return 0;
}

acwing859 : Kruskal(将所有边排序，依次选取最小的边，如果两端点在一个集合，则去判断下一条边；如果两个端点不在一个集合，则将这条边加入集合，最后判断集合中的边数，如果最后极小连通子图的边数小于n-1，则该图不是最小生成树)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int n , m ;
int res , cnt ;
int p[N] ;
struct Node
{
    int a , b , w ;

    bool operator < (const Node & t) const
    {
        return w < t.w;
    }
}node[2 * N];

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

int kruskal()
{

    for (int i = 0 ; i < m ; i ++)
    {
        int a = node[i].a , b = node[i].b , w = node[i].w ;
        if (find(a) != find(b))
        {
            res += w ;
            cnt ++ ;
            p[find(a)] = find(b);
        }
    }

    if (cnt < n -1) return 0x3f3f3f3f ;
    else return res ;
}

int main()
{
    cin >> n >> m;

    for (int i = 1 ; i <= n ; i ++) p[i] = i ;

    //注意node下标如果不是从i=0开始直接sort会出错，因为sort(node , node + m) 是从node首地址即0
    //如果是从下标i开始，则sort应该(node + i , node + m );
    for (int i = 0 ; i < m ; i ++) 
    {
        int a , b , w;
        cin >> a >> b >> w ;
        node[i] = {a , b , w};
    }
    sort(node , node + m);

    int t = kruskal();

    if (t == 0x3f3f3f3f) puts("impossible");
    else cout << t << endl ;

    return 0;
}

0 评论

App 内打开

二刷算法基础课(图论)

multiset存放具体方案,用for输出

acwing842：dfs:递归

acwing844:bfs：队列

最短路径：若权值相等可以用bfs求最短路 ； 权值不等用dijkstra、bellman-ford、spfa、floyd，其中dijkstra不能处理负边，floyd不能处理负环

acwing847 : bfs(权值相等)

acwing847: dijkstra//需要注意堆优化使用到的优先队列默认是大根堆，需要再改成小根堆。

acwing853: bellman_ford(可以用来判断有没有负环(但这个负环得能从1这个起点走到)，但不能解决负环，每次松弛操作时使用的是上一次的dist数组(backup数组)，为了避免发生串联 )

spfa(只要一个点的dist被更新就用该点去检查是否能更新别的边)(可以判断是否存在负环)

与bellman_ford相比：spfa只用更新过dist的点去更新其他点，而bellman_ford每次都会遍历所有边.

与dijkstra堆优化，bfs(都用到队列)相比：dijkstra每次用dist最短的点去更新别的点，而spfa则是每次用队头(被更新过的点，但不一定dist最短)，spfa更类似于优化bfs只能求权值相等的最短路的缺点.

acwing851：spfa求最短路

acwing852 : spfa判负环

acwing848 : 拓扑排序

bfs

dfs

acwing854 : floyd(求多源最短路，不能解决负环图)

acwing858 : Prim(每次选距离集合最近的点(且不在集合内)，用这个点去更新集合外的点距离集合的距离)

0 评论

最短路径：若权值相等可以用bfs求最短路；权值不等用dijkstra、bellman-ford、spfa、floyd，其中dijkstra不能处理负边，floyd不能处理负环