信息学奥赛一本通 1488：新的开始

【题目链接】

ybt 1488：新的开始

【题目考点】

1. 图论：最小生成树

• Prim算法
• Kruskal算法

【解题思路】

每个矿井是一个顶点，第i口矿井到第j口矿井建立电网的费用就是第i顶点到第j顶点边的权值，该图是无向图。
对于每个矿井，可以建发电站，也可以建一条线路，将该矿井连接到一个已供电的网络。
在第i矿井建立发电站，需要费用$v_i$。考虑将建发电站也转化成一种建立线路的操作。
那么可以假想存在一个特殊的地点，比如第0号矿井，记为顶点0，第0号矿井已供电。
假设从第0矿井到第i矿井建立一条线路的费用为$v_i$，那么从第0矿井到第i矿井建立一条线路的操作，和在第i矿井建发电站的操作，都可以为第i矿井供电，效果是一样的。
因此建图时，增加顶点0。如果在第i矿井建发电站需要费用$v_i$，那么建一条从顶点0到顶点i的权值为$v_i$的边。
在整个图中选择一些边，使得所有顶点连通，而且要求选择边的权值加和（总费用）最小。由于顶点0是最小生成树中的一个顶点，那么所有矿井都会被供电。
求该图的最小生成树，即可满足需求。最小总花费为最小生成树中边的权值加和。

可以使用Prim算法或Kruskal算法。

【题解代码】

解法1：Prim算法

#include <bits/stdc++.h>
using namespace std;
#define N 305
struct Edge
{int v, w;
};
vector<Edge> edge[N];
int n, sum, dis[N];
bool vis[N];
void prim()
{memset(dis, 0x3f, sizeof(dis));dis[0] = 0;for(int k = 0; k <= n; ++k){int u = -1;for(int i = 0; i <= n; ++i)if(!vis[i] && (u == -1 || dis[u] > dis[i]))u = i;vis[u] = true;sum += dis[u];for(Edge e : edge[u]){int v = e.v, w = e.w;if(!vis[v] && dis[v] > w)dis[v] = w;}}
}
int main()
{int w;cin >> n;for(int i = 1; i <= n; ++i){cin >> w;edge[0].push_back(Edge{i, w});edge[i].push_back(Edge{0, w});}for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){cin >> w;if(j > i)//只看矩阵右上三角{edge[i].push_back(Edge{j, w});edge[j].push_back(Edge{i, w}); }}prim();cout << sum;return 0;
}

解法2：Kruskal算法

#include <bits/stdc++.h>
using namespace std;
#define N 5005
struct Edge
{int u, v, w;//(u, v)权值w的边 bool operator < (const Edge &b) const{return w < b.w;}
};
vector<Edge> edges;
int n, m, sum, fa[N];//fa[i]：i的双亲
void init(int n)
{for(int i = 0; i <= n; ++i)fa[i] = i;
}
int find(int x)//查找x所在集合的根结点
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)//合并 
{fa[find(x)] = find(y);
}
void kruskal()
{int edgeNum = 0;sort(edges.begin(), edges.end());for(Edge e : edges){int u = e.u, v = e.v, w = e.w;if(find(u) != find(v)){sum += w;merge(u, v);if(++edgeNum == n)break;}}
}
int main()
{int n, w;cin >> n;init(n); for(int i = 1; i <= n; ++i){cin >> w;edges.push_back(Edge{0, i, w});}for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j){cin >> w;if(j > i)edges.push_back(Edge{i, j, w});}kruskal();cout << sum;	return 0;
}