光明网站开发,质监站网址,平面设计师务所,个人怎样建设网站目录 1 介绍2 训练 1 介绍
本专题用来记录使用prim算法或kruskal算法求解的题目。
2 训练
题目1#xff1a;1140最短网络
C代码如下#xff0c;
#include iostream
#include cstringusing namespace std;const int N 110, INF 0x3f3f3f3f;
int g[N][N… 目录 1 介绍2 训练 1 介绍
本专题用来记录使用prim算法或kruskal算法求解的题目。
2 训练
题目11140最短网络
C代码如下
#include iostream
#include cstringusing namespace std;const int N 110, INF 0x3f3f3f3f;
int g[N][N];
int d[N];
bool st[N];
int n, m;void prim() {memset(d, 0x3f, sizeof d);int res 0;for (int i 0; i n; i) {int t -1;for (int j 1; j n; j) {if (!st[j] (t -1 || d[t] d[j])) {t j;}}st[t] true;if (i) res d[t];for (int j 1; j n; j) {if (d[j] g[t][j]) {d[j] g[t][j];}}}cout res endl;return;
}int main() {cin n;for (int i 1; i n; i) {for (int j 1; j n; j) {cin g[i][j];}}prim();return 0;
}题目21141局域网
C代码如下
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, M 210;
int p[N];
int n, m;struct Edge {int a, b, w;bool operator (const Edge W) const {return w W.w;}
}edges[M];int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main() {cin n m;int s 0;for (int i 0; i m; i) {cin edges[i].a edges[i].b edges[i].w;s edges[i].w;}for (int i 1; i n; i) p[i] i;sort(edges, edges m);int res 0, cnt 0;for (int i 0; i m; i) {int a edges[i].a, b edges[i].b, w edges[i].w;a find(a);b find(b);if (a ! b) {p[a] b;res w;cnt;}}cout s - res endl;return 0;
}题目31142繁忙的都市
C代码如下
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 310, M 8010;
int n, m;
int p[N];struct Edge {int a, b, w;bool operator (const Edge W) const {return w W.w;}
}edges[M];int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main() {cin n m;for (int i 1; i n; i) p[i] i;for (int i 0; i m; i) {cin edges[i].a edges[i].b edges[i].w;}sort(edges, edges m);int res 0;int cnt 0;for (int i 0; i m; i) {int a edges[i].a, b edges[i].b, w edges[i].w;a find(a);b find(b);if (a ! b) {p[a] b;cnt 1;res w;}}cout cnt res endl;return 0;
}题目4
