A28833. 联络员(liaison)
题目描述
联络员(liaison)
题目描述
Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。
目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。
输入
第一行n，m表示Tyvj一共有n个管理员，有m个通信渠道;
第二行到m+1行，每行四个非负整数，p,u,v,w 当p=1时，表示这个通信渠道为必选通信渠道；当p=2时，表示这个通信渠道为选择性通信渠道；u,v,w表示本条信息描述的是u，v管理员之间的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示费用。
输出
最小的通信费用。
输入样例
5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5输出样例
9提示
样例解释
1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通2号和5号管理员，选择费用为5的渠道，所以总的费用为9。
注意
U,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠道
数据范围
对于30%的数据，n≤10,m≤100;
对于50%的数据, n≤200,m≤1000
对于100%的数据，n≤2000,m≤10000
参考答案
#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;
}答案解析
管理员是顶点，通信渠道是边，要使管理员两两都可以联络，就是使任何两个顶点之间有路径，也就是让整个图是连通图。每选择一个通信渠道，就是选择一条边。该问题可以抽象为：无向图中给定n个顶点，和m条边，有一些必选边，在其它可选边中选择一些边，使得顶点和选择出来的边构成一个连通图，求在不同选择边的方案中，求选择的边的权值加和的最小值。
选择必选边后，一些顶点连通，构成一些连通分量。一个单独的顶点也是连通分量。现在可以将每个连通分量当做一个顶点，即缩点，要想在非必选边中选择权值加和最小的边，使整个图连通，那么就是在求缩点后的图的最小生成树。
实际写代码不用进行缩点，先将所有必选边相连的顶点合并集合，而后再跑Kruskal算法，每次循环选权值最小的未选边，如果其连接的两个顶点不在同一集合（连通分量）中，亦即添加该边后不会形成环，就将两顶点所在集合合并。统计所有选择的边的权值加和，即为结果。