信息学奥赛一本通 1393：联络员(liaison)

编程基础 • 2025-01-03 15:17 • 阅读 13

【题目链接】

ybt 1393：联络员(liaison)

【题目考点】

1. 图论：最小生成树

【解题思路】

管理员是顶点，通信渠道是边，要使管理员两两都可以联络，就是使任何两个顶点之间有路径，也就是让整个图是连通图。每选择一个通信渠道，就是选择一条边。该问题可以抽象为：无向图中给定n个顶点，和m条边，有一些必选边，在其它可选边中选择一些边，使得顶点和选择出来的边构成一个连通图，求在不同选择边的方案中，求选择的边的权值加和的最小值。
选择必选边后，一些顶点连通，构成一些连通分量。一个单独的顶点也是连通分量。现在可以将每个连通分量当做一个顶点，即缩点，要想在非必选边中选择权值加和最小的边，使整个图连通，那么就是在求缩点后的图的最小生成树。
实际写代码不用进行缩点，先将所有必选边相连的顶点合并集合，而后再跑Kruskal算法，每次循环选权值最小的未选边，如果其连接的两个顶点不在同一集合（连通分量）中，亦即添加该边后不会形成环，就将两顶点所在集合合并。统计所有选择的边的权值加和，即为结果。

【题解代码】

解法1：Kruskal算法

#include <bits/stdc++.h> using namespace std; #define N 2005 struct Edge { 
    int u, v, w; bool operator < (const Edge &b) const { 
    return w < b.w; } }; int fa[N], ans; vector<Edge> edges; void initFa(int n) { 
    for(int i = 1; i <= n; ++i) fa[i] = i; } int find(int x) { 
    return x == fa[x] ? x : fa[x] = find(fa[x]); } void merge(int x, int y) { 
    fa[find(x)] = find(y); } void kruskal() { 
    sort(edges.begin(), edges.end()); for(Edge e : edges) { 
    int u = e.u, v = e.v, w = e.w; if(find(u) != find(v)) { 
    merge(u, v); ans += w; } } } int main() { 
    int n, m, p, u, v, w; cin >> n >> m; initFa(n); for(int i = 1; i <= m; ++i) { 
    cin >> p >> u >> v >> w; if(p == 1)//必选  { 
    merge(u, v); ans += w; } else edges.push_back(Edge{ 
   u, v, w}); } kruskal(); cout << ans; return 0; }

今天的文章信息学奥赛一本通 1393：联络员(liaison)分享到此就结束了，感谢您的阅读。