当前位置： 首页 > news >正文

数据结构与算法-图论-复习1（单源最短路，全源最短路，最小生成树）

news 来源：原创 2025/9/19 15:51:24

1. 单源最短路

单一边权 BFS

原理：由于边权为单一值，可使用广度优先搜索（BFS）来求解最短路。BFS 会逐层扩展节点，由于边权相同，第一次到达某个节点时的路径长度就是最短路径长度。

用法：适用于边权都为 1 的图，可快速求出从源点到其他所有节点的最短路径。

代码：

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

const int MAXN = 100005;

vector<int> adj[MAXN];int dist[MAXN];

void bfs(int s) {

    queue<int> q;

    fill(dist, dist + MAXN, -1);

    dist[s] = 0;

    q.push(s);

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        for (int v : adj[u]) {

            if (dist[v] == -1) {

                dist[v] = dist[u] + 1;

                q.push(v);

            }

        }

    }}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v;

        cin >> u >> v;

        adj[u].push_back(v);

        adj[v].push_back(u);

    }

    bfs(s);

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

        cout << dist[i] << " ";

    }

    cout << endl;

    return 0;

}

0 - 1 边权双端队列 BFS

原理：使用双端队列来优化 BFS 过程。对于边权为 0 的边，将其终点插入队头；对于边权为 1 的边，将其终点插入队尾。这样能保证队列中元素的距离是单调递增的。

用法：适用于图中边权只有 0 和 1 的情况。

代码：

#include <iostream>#include <deque>#include <vector>using namespace std;

const int MAXN = 100005;

vector<pair<int, int>> adj[MAXN];int dist[MAXN];

void bfs_01(int s) {

    deque<int> q;

    fill(dist, dist + MAXN, -1);

    dist[s] = 0;

    q.push_back(s);

    while (!q.empty()) {

        int u = q.front();

        q.pop_front();

        for (auto [v, w] : adj[u]) {

            if (dist[v] == -1) {

                dist[v] = dist[u] + w;

                if (w == 0) {

                    q.push_front(v);

                } else {

                    q.push_back(v);

                }

            }

        }

    }}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        adj[u].emplace_back(v, w);

        adj[v].emplace_back(u, w);

    }

    bfs_01(s);

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

        cout << dist[i] << " ";

    }

    cout << endl;

    return 0;

}

朴素迪杰斯特拉

原理：通过贪心策略，每次从未确定最短路径的节点中选择距离源点最近的节点，然后以该节点为中间点更新其他节点的距离。

用法：适用于边权非负且节点数较少的图，时间复杂度为 O(V2)稠密图。

代码：

#include <iostream>#include <vector>#include <climits>using namespace std;

const int MAXN = 1005;int graph[MAXN][MAXN];int dist[MAXN];bool vis[MAXN];

void dijkstra(int s, int n) {

    fill(dist, dist + MAXN, INT_MAX);

    fill(vis, vis + MAXN, false);

    dist[s] = 0;

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

        int u = -1;

        for (int j = 1; j <= n; j++) {

            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {

                u = j;

            }

        }

        vis[u] = true;

        for (int v = 1; v <= n; v++) {

            if (!vis[v] && graph[u][v] != INT_MAX) {

                dist[v] = min(dist[v], dist[u] + graph[u][v]);

            }

        }

    }}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

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

        for (int j = 1; j <= n; j++) {

            if (i == j) {

                graph[i][j] = 0;

            } else {

                graph[i][j] = INT_MAX;

            }

        }

    }

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        graph[u][v] = min(graph[u][v], w);

    }

    dijkstra(s, n);

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

        cout << dist[i] << " ";

    }

    cout << endl;

    return 0;}

堆优化迪杰斯特拉

原理：使用优先队列（小根堆）来优化每次选择距离源点最近的节点的过程，减少时间复杂度。

用法：适用于边权非负且节点数较多的稀疏图，时间复杂度为 O((V+E)logV)。

代码：

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;

const int MAXN = 100005;

vector<pair<int, int>> adj[MAXN];int dist[MAXN];

void dijkstra(int s) {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    fill(dist, dist + MAXN, INT_MAX);

    dist[s] = 0;

    pq.push({0, s});

    while (!pq.empty()) {

        auto [d, u] = pq.top();

        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {

            if (dist[v] > dist[u] + w) {

                dist[v] = dist[u] + w;

                pq.push({dist[v], v});

            }

        }

    }}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        adj[u].emplace_back(v, w);

    }

    dijkstra(s);

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

        cout << dist[i] << " ";

    }

    cout << endl;

    return 0;}

Bellman - Ford

原理：通过对所有边进行 V−1 次松弛操作，来更新节点的最短距离。如果图中存在负环，经过 V−1 次松弛操作后，仍然可以继续松弛。

用法：适用于存在负权边的图，也可用于求解只经过 k 条边的最短路。

代码：

#include <iostream>#include <vector>#include <climits>using namespace std;

const int MAXN = 100005;struct Edge {

    int u, v, w;};

vector<Edge> edges;int dist[MAXN];

bool bellman_ford(int s, int n) {

    fill(dist, dist + MAXN, INT_MAX);

    dist[s] = 0;

     int flag=0;

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

        for (auto [u, v, w] : edges) {

            flag=0;

            if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {

                dist[v] = dist[u] + w;

                 flag=1;

                 if(i==n)return true;//如果链接了n条边还能松弛就说明有负环

            }

        }

    }

    return false;

}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        edges.push_back({u, v, w});

    }

    if (bellman_ford(s, n)) {

        cout << "存在负环" << endl;

    } else {

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

            cout << dist[i] << " ";

        }

        cout << endl;

    }

    return 0;

}

SPFA

原理：SPFA 是 Bellman - Ford 算法的优化版本，使用队列来维护需要松弛的节点。

用法：适用于存在负权边的图，但在某些特殊图中可能会退化为 O(VE)。

代码：

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;

const int MAXN = 100005;

vector<pair<int, int>> adj[MAXN];int dist[MAXN];int cnt[MAXN]; // 记录每个节点入队的次数bool in_queue[MAXN];

bool spfa(int s, int n) {

    fill(dist, dist + MAXN, INT_MAX);

    fill(cnt, cnt + MAXN, 0);

    fill(in_queue, in_queue + MAXN, false);

    dist[s] = 0;

    queue<int> q;

    q.push(s);

    in_queue[s] = true;

    cnt[s] = 1;

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        in_queue[u] = false;

        for (auto [v, w] : adj[u]) {

            if (dist[v] > dist[u] + w) {

                dist[v] = dist[u] + w;

                if (!in_queue[v]) {

                    q.push(v);

                    in_queue[v] = true;

                    cnt[v]++;

                    if (cnt[v] > n) {

                        return true; // 存在负环

                    }

                }

            }

        }

    }

    return false;}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        adj[u].emplace_back(v, w);

    }

    if (spfa(s, n)) {

        cout << "存在负环" << endl;

    } else {

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

            cout << dist[i] << " ";

        }

        cout << endl;

    }

    return 0;}

2. 单源最短路和其他算法的结合

二分答案 + 双端队列求最短路

以 “可以免费建立 k 条边，求最小的花费” 为例，二分答案 mid，将边权大于 mid 的边视为 1，边权小于等于 mid 的边视为 0，使用双端队列 BFS 求解最短路，判断最短路径上大于 mid 的边数是否小于等于 k。

缩点 + 最短路

先使用 Tarjan 算法求出图的强连通分量，然后进行缩点，将每个强连通分量缩成一个点，再在缩点后的图上进行最短路计算。

首位两次最短路求节点之间的最大差值（以 2009 年提高组最优贸易问题为例）

分别从起点和终点进行最短路计算，记录从起点到每个节点的最小价格和从终点到每个节点的最大价格，然后枚举每个节点，计算最大差值。

3. 单源最短路自身的拓展

多起点多终点用虚拟节点

添加一个虚拟起点和一个虚拟终点，将虚拟起点与所有起点相连，边权为 0，将所有终点与虚拟终点相连，边权为 0，然后求解从虚拟起点到虚拟终点的最短路。

分图层的最短路

以 “拯救大兵瑞恩” 为例，使用三维数组 d[x][y][st] 记录状态，其中 (x,y) 表示节点坐标，st 表示当前拥有的钥匙状态，只有拿到了钥匙才能进入到对应层的一些状态，在 BFS 或 Dijkstra 过程中更新状态。

新的一个例题：

题目背景
本题原题数据极弱，Subtask 0 中的测试点为原题测试点，Subtask 1 中的测试点为 Hack 数据。

题目描述
C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。

C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1∼n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

假设 1∼n 号城市的水晶球价格分别为 4,3,5,6,1。

阿龙可以选择如下一条线路：1→2→3→5，并在 2 号城市以 3 的价格买入水晶球，在 3 号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。

阿龙也可以选择如下一条线路：1→4→5→4→5，并在第 1 次到达 5 号城市时以 1 的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。

现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

输入格式
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。

接下来 m 行，每行有 3 个正整数 x,y,z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。

输出格式
一个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 0。

代码：

分层图，第一层原本的图，第二层，第一层购买后到达的图，第三层，第二层对应节点卖出的图

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=100010;
unordered_map<int,vector<pii>>e;
int n,m;
int a[N];
int dis[N*3];
bool vis[N*3];
void spfa(int s){
    memset(dis,-0x3f,sizeof dis);
    queue<int> q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto t:e[u]){
            int v=t.first,w=t.second;
            if(dis[v]<dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        e[i].push_back({i+n,-a[i]});
        e[n+i].push_back({i+2*n,a[i]});
    }
    for(int i=0;i<m;i++){
        int u,v,op;
        scanf("%d%d%d",&u,&v,&op);
        if(op==2){
            e[u].push_back({v,0});
            e[u+n].push_back({v+n,0});
            e[u+2*n].push_back({v+2*n,0});
            e[v].push_back({u,0});
            e[v+n].push_back({u+n,0});
            e[v+2*n].push_back({u+2*n,0});
        }else{
            e[u].push_back({v,0});
            e[u+n].push_back({v+n,0});
            e[u+2*n].push_back({v+2*n,0});
        }
    }
    spfa(1);
    cout<<dis[3*n];
}
 

最短路计数

在更新最短路径时，记录路径数量。如果经过某个点的路径更短，计数为 1；如果相等，计数累加。

代码：

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;

const int MAXN = 100005;const int MOD = 1e9 + 7;

vector<pair<int, int>> adj[MAXN];int dist[MAXN];int cnt[MAXN];

void dijkstra(int s) {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    fill(dist, dist + MAXN, INT_MAX);

    fill(cnt, cnt + MAXN, 0);

    dist[s] = 0;

    cnt[s] = 1;

    pq.push({0, s});

    while (!pq.empty()) {

        auto [d, u] = pq.top();

        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {

            if (dist[v] > dist[u] + w) {

                dist[v] = dist[u] + w;

                cnt[v] = cnt[u];

                pq.push({dist[v], v});

            } else if (dist[v] == dist[u] + w) {

                cnt[v] = (cnt[v] + cnt[u]) % MOD;

            }

        }

    }}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        adj[u].emplace_back(v, w);

    }

    dijkstra(s);

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

        cout << dist[i] << " " << cnt[i] << endl;

    }

    return 0;}

最短路和次短路

使用两个数组分别记录最短路和次短路，在更新时同时更新这两个数组。

代码：

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;

const int MAXN = 100005;

vector<pair<int, int>> adj[MAXN];int dist1[MAXN]; // 最短路int dist2[MAXN]; // 次短路

void dijkstra(int s) {

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    fill(dist1, dist1 + MAXN, INT_MAX);

    fill(dist2, dist2 + MAXN, INT_MAX);

    dist1[s] = 0;

    pq.push({0, s});

    while (!pq.empty()) {

        auto [d, u] = pq.top();

        pq.pop();

        if (d > dist2[u]) continue;

        for (auto [v, w] : adj[u]) {

            int new_dist = d + w;

            if (new_dist < dist1[v]) {

                dist2[v] = dist1[v];

                dist1[v] = new_dist;

                pq.push({dist1[v], v});

            } else if (new_dist < dist2[v] && new_dist > dist1[v]) {

                dist2[v] = new_dist;

                pq.push({dist2[v], v});

            }

        }

    }}

int main() {

    int n, m, s;

    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        adj[u].emplace_back(v, w);

    }

    dijkstra(s);

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

        cout << dist1[i] << " " << dist2[i] << endl;

    }

    return 0;}

4. 全源最短路

Floyd 算法

原理：通过动态规划的思想，枚举中间节点 k，更新任意两点之间的最短距离。

用法：适用于求解任意两点之间的最短路径，也可用于处理联通问题、传递闭包和最小环问题。

代码：

#include <iostream>#include <climits>using namespace std;

const int MAXN = 1005;int graph[MAXN][MAXN];

void floyd(int n) {

    for (int k = 1; k <= n; k++) {

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

            for (int j = 1; j <= n; j++) {

                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX) {

                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

                }

            }

        }

    }}

int main() {

    int n, m;

    cin >> n >> m;

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

        for (int j = 1; j <= n; j++) {

            if (i == j) {

                graph[i][j] = 0;

            } else {

                graph[i][j] = INT_MAX;

            }

        }

    }

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        graph[u][v] = min(graph[u][v], w);

    }

    floyd(n);

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

        for (int j = 1; j <= n; j++) {

            cout << graph[i][j] << " ";

        }

        cout << endl;

    }

    return 0;}

最小环

在 Floyd 算法的基础上，记录最小环的长度。

cpp

#include <iostream>#include <climits>using namespace std;

const int MAXN = 1005;int graph[MAXN][MAXN];int dist[MAXN][MAXN];

int floyd_min_cycle(int n) {

    int ans = INT_MAX;

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

        for (int j = 1; j <= n; j++) {

            dist[i][j] = graph[i][j];

        }

    }

    for (int k = 1; k <= n; k++) {

        for (int i = 1; i < k; i++) {

            for (int j = i + 1; j < k; j++) {

                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX && dist[i][j] != INT_MAX) {

                    ans = min(ans, graph[i][k] + graph[k][j] + dist[i][j]);

                }

            }

        }

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

            for (int j = 1; j <= n; j++) {

                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {

                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

                }

            }

        }

    }

    return ans;

}

int main() {

    int n, m;

    cin >> n >> m;

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

        for (int j = 1; j <= n; j++) {

            if (i == j) {

                graph[i][j] = 0;

            } else {

                graph[i][j] = INT_MAX;

            }

        }

    }

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        graph[u][v] = min(graph[u][v], w);

        graph[v][u] = min(graph[v][u], w);

    }

    int min_cycle = floyd_min_cycle(n);

    if (min_cycle == INT_MAX) {

        cout << "不存在最小环" << endl;

    } else {

        cout << "最小环长度为: " << min_cycle << endl;

    }

    return 0;

}

5. 最小生成树

Prim 算法

原理：从一个节点开始，每次选择与当前生成树相连的边中权值最小的边，将其加入生成树，直到所有节点都被加入。

用法：适用于稠密图，时间复杂度为 O(V2)。

代码：

#include <iostream>#include <vector>#include <climits>using namespace std;

const int MAXN = 1005;int graph[MAXN][MAXN];bool vis[MAXN];int dist[MAXN];

int prim(int n) {

    fill(vis, vis + MAXN, false);

    fill(dist, dist + MAXN, INT_MAX);

    dist[1] = 0;

    int ans = 0;

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

        int u = -1;

        for (int j = 1; j <= n; j++) {

            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {

                u = j;

            }

        }

        vis[u] = true;

        ans += dist[u];

        for (int v = 1; v <= n; v++) {

            if (!vis[v] && graph[u][v] != INT_MAX) {

                dist[v] = min(dist[v], graph[u][v]);

            }

        }

    }

    return ans;}

int main() {

    int n, m;

    cin >> n >> m;

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

        for (int j = 1; j <= n; j++) {

            if (i == j) {

                graph[i][j] = 0;

            } else {

                graph[i][j] = INT_MAX;

            }

        }

    }

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        graph[u][v] = min(graph[u][v], w);

        graph[v][u] = min(graph[v][u], w);

    }

    int mst = prim(n);

    cout << "最小生成树的权值为: " << mst << endl;

    return 0;}

Kruskal 算法

原理：将所有边按权值从小到大排序，然后依次选择边，如果该边的两个端点不在同一个连通分量中，则将该边加入生成树，直到所有节点都在同一个连通分量中。

用法：适用于稀疏图，时间复杂度为 O(ElogE)。

代码：

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

const int MAXN = 100005;struct Edge {

    int u, v, w;

    bool operator<(const Edge& other) const {

        return w < other.w;

    }};

vector<Edge> edges;int parent[MAXN];

int find(int x) {

    if (parent[x] != x) {

        parent[x] = find(parent[x]);

    }

    return parent[x];}

void unite(int x, int y) {

    int px = find(x);

    int py = find(y);

    if (px != py) {

        parent[px] = py;

    }}

int kruskal(int n) {

    sort(edges.begin(), edges.end());

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

        parent[i] = i;

    }

    int ans = 0;

    int cnt = 0;

    for (auto [u, v, w] : edges) {

        if (find(u) != find(v)) {

            unite(u, v);

            ans += w;

            cnt++;

            if (cnt == n - 1) {

                break;

            }

        }

    }

    return ans;}

int main() {

    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        edges.push_back({u, v, w});

    }

    int mst = kruskal(n);

    cout << "最小生成树的权值为: " << mst << endl;

    return 0;}

6. 最小生成树的运用

引入虚拟节点

以 “有 k 个点可以用卫星链接，求出让全部点联通的最小花费” 为例，添加一个虚拟节点，将该节点与可以用卫星链接的 k 个点相连，边权为 0，然后使用 Kruskal 或 Prim 算法求解最小生成树。

允许 k 个联通块的最小花费

使用 Kruskal 算法，在合并节点的过程中，当合并到 k 个联通块时停止，此时的花费即为最小花费。

代码：

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

const int MAXN = 100005;struct Edge {

    int u, v, w;

    bool operator<(const Edge& other) const {

        return w < other.w;

    }};

vector<Edge> edges;int parent[MAXN];

int find(int x) {

    if (parent[x] != x) {

        parent[x] = find(parent[x]);

    }

    return parent[x];}

void unite(int x, int y) {

    int px = find(x);

    int py = find(y);

    if (px != py) {

        parent[px] = py;

    }}

int kruskal(int n, int k) {

    sort(edges.begin(), edges.end());

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

        parent[i] = i;

    }

    int ans = 0;

    int cnt = n;

    for (auto [u, v, w] : edges) {

        if (find(u) != find(v)) {

            unite(u, v);

            ans += w;

            cnt--;

            if (cnt == k) {

                break;

            }

        }

    }

    return ans;}

int main() {

    int n, m, k;

    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        edges.push_back({u, v, w});

    }

    int cost = kruskal(n, k);

    cout << "允许 " << k << " 个联通块的最小花费为: " << cost << endl;

return 0;

}

相关文章：

数据结构与算法-图论-复习1（单源最短路，全源最短路，最小生成树）

1. 单源最短路 单一边权 BFS 原理&#xff1a;由于边权为单一值&#xff0c;可使用广度优先搜索&#xff08;BFS&#xff09;来求解最短路。BFS 会逐层扩展节点&#xff0c;由于边权相同&#xff0c;第一次到达某个节点时的路径长度就是最短路径长度。 用法&#xff1a;适用…...

编程日记 2025/9/19 15:51:25

uniapp：微信小程序，一键获取手机号

<button open-type"getPhoneNumber" getphonenumber"getphonenumber">一键获取</button> <script>export default {methods: {getphonenumber(e){uni.login({provider: weixin,success: (res)> {console.log(res);},});},}} </scr…...

编程日记 2025/9/19 9:50:38

协作焊接机器人

一、核心定义与核心特点 1. 定义 协作焊接机器人是基于协作机器人本体（具备力传感、轻量化、安全停机等特性），集成焊接电源、焊枪、视觉 / 电弧传感器等模块，实现人机共融焊接作业的自动化设备。其核心在于： 安全协作：支持与焊工共同工作，无需物理隔离；柔性适配：快速…...

编程日记 2025/9/11 15:25:08

SpringBoot和微服务学习记录Day2

微服务 微服务将单体应用分割成更小的的独立服务&#xff0c;部署在不同的服务器上。服务间的关联通过暴露的api接口来实现 优点&#xff1a;高内聚低耦合&#xff0c;一个模块有问题不影响整个应用&#xff0c;增加可靠性&#xff0c;更新技术方便 缺点&#xff1a;增加运维…...

编程日记 2025/9/18 17:28:57

【CornerTag组件详解：优雅的角标设计与实现】

CornerTag组件详解&#xff1a;优雅的角标设计与实现 组件完整代码 <template><divclass"corner-tag":style"{background: bgColor,padding: ${paddingY}px 0,fontSize: fontSize px,...customStyle}"><slot /></div> </tem…...

编程日记 2025/9/17 12:36:18

Mybatis-缓存详解

什么是缓存&#xff1f; 存在内存中的临时数据 将用户经常查询的数据放在缓存中&#xff0c;用户去查询数据就不用从磁盘上&#xff08;关系型数据库数据文件&#xff09;查询&#xff0c;从缓存中查询&#xff0c;从而提高查询效率&#xff0c;解决了高并发系统的性能问题 经…...

编程日记 2025/9/17 22:44:26

WHAT - React useId vs uuid

目录 uuiduseId适用场景语法示例注意事项 复杂示例示例&#xff1a;动态表单列表 useId解读重点 useId vs uuid一句话总结对比表格示例对比useId 用于表单uuid() 用在 UI 会出问题uuid 的适合场景 总结建议 uuid 在 WHAT - Math.random&#xff1f;伪随机&#xff1f; 中我们…...

编程日记 2025/9/18 19:04:09

Leetcode 跳跃游戏 II （贪心算法）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 < j < nums[i] i j < n 返回到达 nums[n - 1] 的最…...

编程日记 2025/9/19 11:54:26

银河麒麟V10 Ollama+ShellGPT打造Shell AI助手——筑梦之路

环境说明 1. 操作系统版本: 银河麒麟V10 2. CPU架构&#xff1a;X86 3. Python版本&#xff1a;3.12.9 4. 大模型&#xff1a;mistral:7b-instruct 准备工作 1. 编译安装python 3.12 # 下载python 源码wget https://www.python.org/ftp/python/3.12.9/Python-3.12.9.tg…...

编程日记 2025/9/19 14:27:37

【物联网】GPT延时

文章目录 前言一、GPT实现延时1. 定时器介绍2. I.MX6ull GPT定时器介绍1&#xff09;GPT定时器工作原理2&#xff09;GPT的输入捕获3&#xff09;GPT的输出比较 3. 高精度延时实现1&#xff09;实现思路 前言 使用 GPT 实现延时控制以及基于 PWM 实现蜂鸣器发声与频率调节这两…...

编程日记 2025/9/19 2:34:27

【套题】大沥2019年真题——第4题

04.数字圈 题目描述 当我们写数字时会发现有些数字有封闭区域&#xff0c;有的数字没有封闭区域。 数字 0 有一个封闭区域&#xff0c;数字 1、2、 3 都没有封闭区域&#xff0c;数字 4 有一个封闭区域&#xff0c;数字 5 没有封闭区域&#xff0c;数字 6 有一个封闭区域&#…...

编程日记 2025/9/16 21:14:26

idea 安装 proxyai 后的使用方法

1. 可以默认使用ProxyAi 安装后使用如下配置可以进行代码提示 配置 使用示例 2. 这里有必要说一下&#xff0c;这里要选择提供服务的ai 选择后才可以使用ProxyAI或者Custom openAI 3. 可以使用custom openAi, 要自行配置 1&#xff09;配置 code completions 这是header …...

编程日记 2025/9/16 11:16:34

构建实时、融合的湖仓一体数据分析平台：基于 Delta Lake 与 Apache Iceberg

1. 执行摘要 挑战&#xff1a; 传统数据仓库在处理现代数据需求时面临诸多限制&#xff0c;包括高昂的存储和计算成本、处理海量多样化数据的能力不足、以及数据从产生到可供分析的端到端延迟过高。同时&#xff0c;虽然数据湖提供了低成本、灵活的存储&#xff0c;但往往缺乏…...

编程日记 2025/9/18 14:19:02

数据库的MVCC机制详解

MVCC&#xff08;Multi-Version Concurrency Control&#xff0c;多版本并发控制&#xff09;是数据库系统中常用的并发控制机制&#xff0c;它允许数据库在同一时间点保存数据的多个版本&#xff0c;从而实现非阻塞的读操作&#xff0c;提高并发性能。 MVCC的核心思想是&…...

编程日记 2025/9/9 13:54:19

未来与自然的交响：蓉城生态诗篇

故事背景 故事发生在中国四川成都&#xff0c;描绘了未来城市中科技与自然共生的奇迹。通过六个极具创意的生态场景&#xff0c;展现人类如何以诗意的方式重构与自然的连接&#xff0c;在竹海保育、文化传承、能源循环等维度编织出震撼心灵的未来图景。 故事内容 当晨雾在竹纤维…...

编程日记 2025/9/19 10:52:07

【愚公系列】《高效使用DeepSeek》062-图书库存管理

🌟【技术大咖愚公搬代码：全栈专家的成长之路，你关注的宝藏博主在这里！】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主！ 👉 江湖人称"愚公搬代码"，用七年如一日的精神深耕技术领域，以"…...

编程日记 2025/9/17 23:30:31

汽车软件开发常用的建模工具汇总

目录 往期推荐 1.Enterprise Architect&#xff08;EA&#xff09; 2.MATLAB/Simulink 3.TargetLink 4.Rational Rhapsody 5.AUTOSAR Builder 6.PREEvision 总结 往期推荐 2025汽车行业新宠&#xff1a;欧企都在用的工具软件ETAS工具链自动化实战指南&#xff1c;一&am…...

编程日记 2025/9/15 20:14:38

六、继承（二）

1 继承与友元 如果一个基类中存在友元关系&#xff0c;那么这个友元关系能不能继承呢&#xff1f; 例&#xff1a; #include <iostream> using namespace std; class Student; class Person { public:friend void Display(const Person& p, const Student& s)…...

编程日记 2025/9/10 9:47:47

flink部署使用(flink-connector-jdbc)连接达梦数据库并写入读取数据

flink介绍 1&#xff09;Apache Flink 是一个框架和分布式处理引擎&#xff0c;用于对无界和有界数据流进行有状态计算。Flink 被设计在所有常见的集群环境中运行&#xff0c;以内存执行速度和任意规模来执行计算。 2&#xff09;在实时计算或离线任务中&#xff0c;往往需要…...

编程日记 2025/9/18 17:11:47

【Rust开发】Rust快速入门，开发出Rust的第一个Hello World

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

编程日记 2025/9/13 13:41:51

Flink框架：批处理和流式处理与有界数据和无界数据之间的关系

本文重点 从数据集的类型来看&#xff0c;数据集可以分为有界数据和无界数据两种&#xff0c;从处理方式来看&#xff0c;有批处理和流处理两种。一般而言有界数据常常使用批处理方式&#xff0c;无界数据往往使用流处理方式。 有界数据和无界数据 有界数据有一个明确的开始和…...

编程日记 2025/9/17 0:29:53

基于 Spring Boot 瑞吉外卖系统开发（四）

基于 Spring Boot 瑞吉外卖系统开发&#xff08;四&#xff09; 新增分类 新增分类UI界面&#xff0c;两个按钮分别对应两个UI界面 两个页面所需的接口都一样&#xff0c;请求参数type值不一样&#xff0c;type1为菜品分类&#xff0c;type2为套餐分类。 请求方法都为POST。…...

编程日记 2025/9/18 11:43:53

患者根据医生编号完成绑定和解绑接口

医疗系统接口文档 一、Controller 层 1. InstitutionDoctorController 医疗机构和医生相关的控制器&#xff0c;提供机构查询、医生查询、绑定解绑医生等功能。 RestController RequestMapping("/institution-doctor") public class InstitutionDoctorController…...

编程日记 2025/9/19 4:43:28

Flutter性能优化终极指南：从JIT到AOT的深度调优

一、Impeller渲染引擎调优策略 1.1 JIT预热智能预编译 // 配置Impeller预编译策略 void configureImpeller() {ImpellerEngine.precacheShaders(shaders: [lib/shaders/skinned_mesh.vert,lib/shaders/particle_system.frag],warmupFrames: 30, // 首屏渲染前预编译帧数cach…...

编程日记 2025/9/18 18:20:27

（1）英特尔 RealSense T265（三）

文章目录 前言 4.4 地面测试 4.5 飞行测试 4.6 室内外实验 4.7 数据闪存记录 4.8 启动时自动运行 4.9 使用 OpticalFlow 进行 EKF3 光源转换 前言 Realsense T265 通过 librealsense 支持 Windows 和 Linux 系统。不同系统的安装过程差异很大&#xff0c;因此请参阅 gi…...

编程日记 2025/9/19 5:38:13

【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;C 目录 前言 一、列表初始化 1. 大括号初始化 2. initializer_list 二、右值引用和移动语义 1. 左值和右值 2. 左值引用和右值引用 引用延长生命周期 左…...

编程日记 2025/9/19 15:40:25

ArcGIS 给大面内小面字段赋值

文章目录 引言：地理数据处理中的自动化赋值为何重要？实现思路模型实现关键点效果实现步骤1、准备数据2、执行3、完成4、效果引言：地理数据处理中的自动化赋值为何重要？ 在地理信息系统（GIS）的日常工作中，空间数据的属性字段赋值是高频且关键的操作，例如在土地利用规划…...

编程日记 2025/9/19 9:22:16

计算机网络——传输层(Udp)

udp UDP&#xff08;User Datagram Protocol&#xff0c;用户数据报协议 &#xff09;是一种无连接的传输层协议&#xff0c;它在IP协议&#xff08;互联网协议&#xff09;之上工作&#xff0c;为应用程序提供了一种发送和接收数据报的基本方式。以下是UDP原理的详细解释&…...

编程日记 2025/9/19 2:58:48

【操作系统（Linux）】——生产者消费者同步互斥模型

✅ 一、程序功能概述 我们将做的&#xff1a;实现一个经典的「生产者-消费者问题」多线程同步模型的案例&#xff0c;主要用到 循环缓冲区 POSIX 信号量 sem_t pthread 多线程库&#xff0c;非常适合理解并发控制、线程通信和缓冲区管理。 案例目标&#xff1a;通过多个生产…...

编程日记 2025/9/16 2:14:28

从数据到洞察：探索数据分析与可视化的高级方法

从数据到洞察：探索数据分析与可视化的高级方法 引言 在今天这个数据驱动的时代，海量的数据只有通过科学分析和清晰可视化，才能转化为商业价值和决策依据。然而，数据分析与可视化远不只是制作几个图表，它需要高级技术、深度洞察力以及良好的工具支持。随着大数据领域的快…...

编程日记 2025/9/19 1:20:16

计算机视觉中的数学：几何变换与矩阵运算详解

计算机视觉中的数学&#xff1a;几何变换与矩阵运算详解 一、前言二、基础数学概念回顾​2.1 向量与向量运算​2.1.1 向量的定义​2.1.2 向量运算​ 2.2 矩阵基础​2.2.1 矩阵的定义与表示​2.2.2 矩阵运算​ 三、几何变换基础​3.1 平移变换​3.1.1 原理​3.1.2 代码示例&…...

编程日记 2025/9/18 15:17:00

华为数字芯片机考2025合集3已校正

1. 题目内容 下列说法正确的是&#xff08;&#xff09;。 1. 解题步骤 1.1 选项分析 选项描述正误依据A异步 FIFO 采用格雷码是为了省功耗✗格雷码用于消除多比特信号跨时钟域的位跳变风险&#xff0c;与功耗无关B单比特信号打两拍可以完全避免亚稳态✗双触发器同步仅降低…...

编程日记 2025/9/17 20:01:57

启山智软的营销方法有哪些优势？

启山智软作为一家科技或软件企业&#xff0c;其营销方法的优势可能体现在以下几个方面&#xff0c;这些优势结合了行业特点与创新策略&#xff0c;帮助其在竞争激烈的市场中占据有利位置&#xff1a; ​​1. 技术驱动的精准营销​​ ​​数据挖掘与AI应用​​&#xff1a; 通…...

编程日记 2025/9/18 10:57:04

openpyxl合并连续相同元素的单元格

文章目录 前言一、openpyxl是什么&#xff1f;二、基础用法1.读取和写入文件2.合并单元格 三、合并单元格实战1.连续相同元素的索引范围2.转换3.获取列合并索引4.整体 总结 前言 python可以很方便的操作各种文档&#xff0c;比如docx&#xff0c;xlsx等。本文主要介绍在xlsx文…...

编程日记 2025/9/18 3:11:27

从零开始学java--泛型（二）

泛型 目录 泛型 泛型与多态 泛型方法 泛型的界限 泛型与多态 不只是类&#xff0c;包括接口、抽象类都可以支持泛型&#xff1a; public static void main(String[] args) {Score<String> scorenew Score<>("数学","aa","优秀"…...

编程日记 2025/9/18 18:12:48

设计模式 Day 6：深入讲透观察者模式（真实场景 + 回调机制 + 高级理解）

观察者模式&#xff08;Observer Pattern&#xff09;是一种设计结构中最实用、最常见的行为模式之一。它的魅力不仅在于简洁的“一对多”事件推送能力&#xff0c;更在于它的解耦能力、模块协作设计、实时响应能力。 本篇作为 Day 6&#xff0c;将带你从理论、底层机制到真实…...

编程日记 2025/9/11 15:52:21

深入理解 Shell：从原理到实战的全方位解析

1. 引言&#xff1a;什么是 Shell&#xff1f; Shell 是操作系统中最基础却最强大的工具之一。它是用户与操作系统之间的接口&#xff0c;一个命令行解释器&#xff0c;它接收用户输入的命令并调用操作系统内核完成相应的操作。 Shell 的含义包括两层&#xff1a; 交互式命令…...

编程日记 2025/9/17 20:53:22

图灵逆向——题六-倚天剑

从第六题开始就要有个先看看请求头的习惯了[doge]。 别问博主为什么要你养成这个习惯&#xff0c;问就是博主被坑过。。。 headers里面有一个加密参数S&#xff0c;然后你就去逆向这个S对吧。 然后一看响应&#xff1a; 好家伙返回的还是个密文&#xff0c;所以要两次逆向咯。…...

编程日记 2025/9/19 7:43:52

【WRF理论第十七期】单向/双向嵌套机制（含namelist.input详细介绍）

WRF运行的单向/双向嵌套机制 准备工作&#xff1a;WRF运行的基本流程namelist.input的详细设置&time_control 设置&domain 嵌套结构&bdy_control 配置部分 namelist 其他注意事项 嵌套说明双向嵌套&#xff08;two-way nesting&#xff09;单向嵌套&#xff08;one…...

编程日记 2025/9/14 21:00:06

【Springboot知识】Springboot进阶-Micrometer指标监控深入解析

文章目录 ​​Micrometer 核心概念与标准指标详解**Micrometer 核心概念与标准指标详解****一、Micrometer 核心概念****二、Micrometer 标准指标****1. JVM 监控指标****2. 系统资源监控****3. HTTP 请求监控****4. 数据库监控****5. 缓存监控** **三、配置与自定义指标****1.…...

编程日记 2025/9/19 11:06:42

Linux 的准备工作

1.root用户登录 首先讲一下root账户怎么登陆 直接 ssh root 公ip地址就可以了 比如我的是腾讯云的 这个就是公ip 下面所有普通用户的操作都是在root账户下进行的 2.普通用户创建 创建用户指令 adduser 用户名 比如说这个指令 我创建了一个ly_centos的普通用户 3.普通用…...

编程日记 2025/9/10 5:24:42

LLM实现模型并行训练：deepspeed 是什么； transformers` 怎么实现模型并行训练吗？

LLM实现模型并行训练：deepspeed 是什么 DeepSpeed是一个由微软开发的深度学习优化库，旨在帮助研究人员和工程师更高效地训练大规模神经网络。它提供了一系列的优化技术，包括混合精度训练、模型并行、数据并行、ZeRO优化等，以提高训练速度、减少内存占用，并支持在多个GPU或…...

编程日记 2025/9/17 16:15:38

STM32 HAL库之EXTI示例代码

外部中断按键控制LED灯 在main.c中 HAL_Init(); 初始化Flash&#xff0c;中断优先级以及HAL_MspInit函数&#xff0c;也就是 stm32f1xx_hal.c 中 HAL_StatusTypeDef HAL_Init(void) {/* Configure Flash prefetch */ #if (PREFETCH_ENABLE ! 0) #if defined(STM32F101x6) || …...

编程日记 2025/8/24 12:38:14

数字人情感表达突破：微表情自动生成的算法革新

——从量子化建模到联邦学习的全链路技术革命 一、行业痛点&#xff1a;传统数字人微表情的“三重困境” 2025年数据显示&#xff0c;83%的虚拟角色因微表情失真导致用户留存率下降&#xff08;头部游戏公司实测数据&#xff09;。传统方案面临核心矛盾&#xff1a; 制作成本…...

编程日记 2025/9/13 18:54:44

Django软删除功能完整指南：构建图书馆项目

Django软删除功能完整指南：构建图书馆项目 推荐超级课程： 本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录 Django软删除功能完整指南：构建图书馆项目第 1 步：安装所需包第 2 步：设置您的 Django…...

编程日记 2025/9/15 16:03:44

联邦学习：AI 与大数据融合的创新力量

在当今数字化时代&#xff0c;人工智能&#xff08;AI&#xff09;和大数据无疑是推动各行业发展的两大核心技术。AI 凭借其强大的数据分析和预测能力&#xff0c;为企业提供了智能化决策支持&#xff1b;大数据则通过海量数据的收集与存储&#xff0c;为 AI 模型的训练提供了丰…...

编程日记 2025/9/18 6:59:09

idea解决tomcat项目页面中文乱码

概述 解决tomcat项目页面中文乱码问题-Dfile.encodingUTF-8 设置...

编程日记 2025/9/10 16:41:20

Android Coil 3 Fetcher大批量Bitmap拼接成1张扁平宽图，Kotlin

Android Coil 3 Fetcher大批量Bitmap拼接成1张扁平宽图&#xff0c;Kotlin <uses-permission android:name"android.permission.WRITE_EXTERNAL_STORAGE" /><uses-permission android:name"android.permission.READ_EXTERNAL_STORAGE" /><u…...

编程日记 2025/9/19 2:14:21

解锁Midjourney创作潜能：超详细提示词（Prompts）分类指南

AI生图自由&#xff01;就来 ChatTools (https://chat.chattools.cn)&#xff0c;畅享Midjourney免费无限绘画。同时体验GPT-4o、Claude 3.7 Sonnet、DeepSeek等强大模型。 为了帮助大家更好地驾驭Midjourney&#xff0c;我们精心整理并分类了大量常用且效果出众的提示词。无论…...

编程日记 2025/9/11 3:43:17

HBuilder运行uni-app程序报错【Error: listen EACCES: permission denied 0.0.0.0:5173】

一、错误提示&#xff1a; 当使用HBuilder运行uni-app项目的时候提示了如下错误❌ 15:11:03.089 项目 project 开始编译 15:11:04.404 请注意运行模式下&#xff0c;因日志输出、sourcemap 以及未压缩源码等原因&#xff0c;性能和包体积&#xff0c;均不及发行模式。 15:11:04…...

编程日记 2025/9/9 10:32:38