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

【题目链接】

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;}elseedges.push_back(Edge{u, v, w});}kruskal();cout << ans;return 0;
}