国外做网站公司能赚钱,百度热词,建的企业网站如何在百度搜到,怎么自己搭建梯子1140. 最短网络 - AcWing题库
农夫约翰被选为他们镇的镇长#xff01;
他其中一个竞选承诺就是在镇上建立起互联网#xff0c;并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路#xff0c;他想把这条线路共享给其他农场。
约翰的农场的编号是1#xf…1140. 最短网络 - AcWing题库
农夫约翰被选为他们镇的镇长
他其中一个竞选承诺就是在镇上建立起互联网并连接到所有的农场。
约翰已经给他的农场安排了一条高速的网络线路他想把这条线路共享给其他农场。
约翰的农场的编号是1其他农场的编号是 2∼n。
为了使花费最少他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表你必须找出能连接所有农场并使所用光纤最短的方案。
输入格式
第一行包含一个整数 n表示农场个数。
接下来 n 行每行包含 n 个整数输入一个对角线上全是0的对称矩阵。 其中第 x1 行 y 列的整数表示连接农场 x 和农场 y 所需要的光纤长度。
输出格式
输出一个整数表示所需的最小光纤长度。
数据范围
3≤n≤100 每两个农场间的距离均是非负整数且不超过100000。
输入样例
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0输出样例
28
解析 prim算法
prim算法的基本想法种一棵树让树从一个节点增长到n个节点 1.初始的时候树只有一个节点没有边初始节点可以是任意一个节点 2.每一轮循环找出一条边把它接到树上 3.整个过程都要保证一个性质 树是连通图 没有回路 4.算法循环次数等于节点数量每一轮循环添加一个节点
具体操作 1.树中只有一个节点任意选这一个节点即可没有边。 2.用集合 U 来保存选中的节点 3.用集合 T 来保存树的边 4.每次循环把一个点和一条边接到树上 e(u,v)表示边的一个节点在集合U中一个不在选出最小的e(u,v) 将e(u,v)加入T,v加入U中 5.返回这棵树
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemapusing namespace std;
typedef long long LL;
const int N 1e2 5;
int n;
int g[N][N];
int v[N],d[N];int prim() {memset(d, 0x3f, sizeof d);//点到生成树的最小距离d[1] 0;int ret 0;for (int i 1; i n; i) {int x -1;for (int j 1; j n; j) {//vis[j]1表示点j在U中//x-1表示可以任选一个点作为初始节点// d[x] d[j]选出最小的e(u,v)的vif (!v[j] (x -1 || d[j] d[x]))x j;}ret d[x];v[x] 1;//更新e(u,v)用x更新所有点到这棵树的最小距离for (int j 1; j n; j) {d[j] min(d[j], g[j][x]);}}return ret;
}int main() {cin n;for (int i 1; i n; i) {for (int j 1; j n; j) {scanf(%d, g[i][j]);}}cout prim() endl;return 0;
}
