【题目链接】
ybt 1391：局域网(net)
【题目考点】
1. 图论：最小生成树
记图中顶点数为V，边数为E文章来源：https://www.toymoban.com/news/detail-650505.html
- Prim算法
复杂度： O ( V 2 ) O(V^2) O(V2) - Prim算法堆优化
复杂度： O ( E l o g E ) O(E log E) O(ElogE) - Kruskal算法
复杂度： O ( E l o g E ) O(E log E) O(ElogE)
【解题思路】
每台电脑是一个顶点，两台电脑间的网线是边。两台电脑间连接的通畅程度
f
(
i
,
j
)
f(i,j)
f(i,j)就是两个顶点之间边的权值。
一个局域网中任何两台电脑都可以连通，也就是说图中任意两顶点之间都有路径。
要使n个顶点的图中任意两顶点之间都有路径，而且没有回路，那么就需要不断去掉边，剩下的图是原图的生成树。
要使得去掉边的权值加和最大，那么就是要求剩下的生成树的所有边的权值加和最小。
因此该题需要求原图的最小生成树，求出最小生成树的边权值加和，用原图所有边的权值加和减去最小生成树的边权值加和，即为去掉的边权值加和的最大值。文章来源地址https://www.toymoban.com/news/detail-650505.html
【题解代码】
解法1：Prim算法
#include <bits/stdc++.h>
using namespace std;
#define N 105
struct Edge
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){}
};
vector<Edge> edge[N];
bool vis[N];//vis[i]:顶点i是否已被选择
int dis[N];//dis[i]:顶点i距离被选择顶点的最小距离
int n, m, sumTree, sumAll;//sumAll：所有边的权值加和 sumTree：最小生成树的权值加和
void prim()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;//先选择顶点1
for(int k = 1; k <= n; ++k)//循环n次，每次取出一个顶点
{
int u = 0;//dis中最小值的下标
for(int i = 1; i <= n; ++i)
if(vis[i] == false && (u == 0 || dis[i] < dis[u]))
u = i;
sumTree += dis[u];
vis[u] = true;
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(vis[v] == false && dis[v] > w)
dis[v] = w;
}
}
}
int main()
{
int f, t, w;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f].push_back(Edge(t, w));
edge[t].push_back(Edge(f, w));
sumAll += w;
}
prim();
cout << sumAll - sumTree;
return 0;
}
解法2：Prim算法堆优化
#include<bits/stdc++.h>
using namespace std;
#define N 105
struct Edge
{
int v, w;
Edge(){}
Edge(int a, int b):v(a),w(b){}
};
struct Pair
{
int v, d;//v：顶点 d：顶点v到已选择顶点的距离
Pair(){}
Pair(int a, int b):v(a), d(b){}
bool operator < (const Pair &b) const
{
return b.d < d;//到已选择顶点距离更小的数对更优先
}
};
vector<Edge> edge[N];//邻接表
int n, m, sumTree, sumAll, dis[N];//dis[i]：顶点i到已经选择的顶点的最小距离
bool vis[N];//vis[i]：顶点i是否已经被选择
void prim()
{
priority_queue<Pair> pq;
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
pq.push(Pair(1, 0));
int visNum = 0;//已经访问的顶点数
while(pq.empty() == false)
{
int u = pq.top().v, d = pq.top().d;
pq.pop();
if(vis[u])
continue;
vis[u] = true;
sumTree += d;//sumTree：最小生成树边权加和
if(++visNum == n)
break;
for(Edge e : edge[u])
{
int v = e.v, w = e.w;
if(vis[v] == false && dis[v] > w)
{
dis[v] = w;
pq.push(Pair(v, dis[v]));
}
}
}
}
int main()
{
int f, t, w;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edge[f].push_back(Edge(t, w));
edge[t].push_back(Edge(f, w));
sumAll += w;//sumAll:所有边权加和
}
prim();
cout << sumAll - sumTree;
return 0;
}
解法3：Kruskal算法
#include<bits/stdc++.h>
using namespace std;
#define N 105
struct Edge
{
int f, t, w;
Edge(){}
Edge(int a, int b, int c):f(a),t(b),w(c){}
};
int n, m, edgeNum, sumTree, sumAll, fa[N];
bool vis[N];
vector<Edge> edges;
bool cmp(Edge a, Edge b)
{
return a.w < b.w;
}
void initFa()
{
for(int i = 1; i <= n; ++i)
fa[i] = i;
}
int find(int x)
{
if(x == fa[x])
return x;
else
return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
fa[find(x)] = find(y);
}
void kruskal()
{
sort(edges.begin(), edges.end(), cmp);
for(Edge e : edges)
{
if(find(e.f) != find(e.t))
{
sumTree += e.w;
merge(e.f, e.t);
if(++edgeNum == n-1)
return;
}
}
}
int main()
{
int f, t, w;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> f >> t >> w;
edges.push_back(Edge(f, t, w));
sumAll += w;
}
initFa();
kruskal();
cout << sumAll - sumTree;
return 0;
}
到了这里，关于信息学奥赛一本通 1391：局域网(net)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
