当前位置：首页 > news >正文

2025.2.8总结

news 来源：原创 2025/5/22 12:21:30

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,MN,M，表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 Xi,Yi,ZiXi,Yi,Zi，表示有一条长度为 ZiZi 的无向边连接结点 Xi,YiXi,Yi。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1复制

4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3

输出 #1复制

7

说明/提示

数据规模：

对于 20%20% 的数据，N≤5N≤5，M≤20M≤20。

对于 40%40% 的数据，N≤50N≤50，M≤2500M≤2500。

对于 70%70% 的数据，N≤500N≤500，M≤104M≤104。

对于 100%100% 的数据：1≤N≤50001≤N≤5000，1≤M≤2×1051≤M≤2×105，1≤Zi≤1041≤Zi≤104。

样例解释：

!https://cdn.luogu.com.cn/upload/pic/2259.png

所以最小生成树的总边权为 2+2+3=72+2+3=7。

**第一次错误原因：**初始化时将dist设置成1e9，而g[i][j]设置成1e5，这样设置初始值，会导致在更新dist时将原本的1e9更新为1e5从达不到判断的效果

源代码：

#include<iostream>
#include<cstring>
using namespace std;
const int MAX_n = 5005;
int dist[MAX_n],g[MAX_n][MAX_n];
bool  state[MAX_n];
int n, m;
int prim() {int res = 0;dist[1] = 0;for (int i = 0; i <= n; i++) {int t = -1;for (int j = 1; j <= n;j++) {if (!state[j] && (t == -1 || dist[t] > dist[j]))t = j;}state[t] = 1;if (dist[t] == 1e9)return 1e9;res += dist[t];for (int j = 1; j <= n; ++j)dist[j] = min(dist[j], g[t][j]);}return res;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {dist[i] = 1e9;for (int j = 1; j <= n; j++) {g[i][j] = 1e5;}}for (int i = 1; i <= m; i++) {int x, y, z;cin >> x >> y >> z;g[x][y] = g[y][x] = min(g[x][y], z);}int t = prim();if (t == 1e9)cout << "orz" << endl;elsecout << t << endl;return 0;
}

**思路：**从结点1开始，t=1，遍历g[t][]找到比原来的权值并赋值给dist数组，重复进行该操作

源代码：

#include<iostream>
#include<cstring>
using namespace std;
const int MAX_n = 5005;
int dist[MAX_n],g[MAX_n][MAX_n];
bool  state[MAX_n];
int n, m;
int prim() {int res = 0;dist[1] = 0;for (int i = 0; i <= n; i++) {int t = -1;for (int j = 1; j <= n;j++) {if (!state[j] && (t == -1 || dist[t] > dist[j]))t = j;}state[t] = 1;if (dist[t] == 1e9)return 1e9;res += dist[t];for (int j = 1; j <= n; ++j)dist[j] = min(dist[j], g[t][j]);}return res;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {dist[i] = 1e9;for (int j = 1; j <= n; j++) {g[i][j] = 1e9;}}for (int i = 1; i <= m; i++) {int x, y, z;cin >> x >> y >> z;g[x][y] = g[y][x] = min(g[x][y], z);}int t = prim();if (t >= 1e9)cout << "orz" << endl;elsecout << t << endl;return 0;
}

题目描述

国防部计划用无线网络连接若干个边防哨所。 2 种不同的通讯技术用来搭建无线网络；

每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所（两边都有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 DD，这是受收发器的功率限制。收发器的功率越高，通话距离 DD 会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 DD。你的任务是确定收发器必须的最小通话距离 DD，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

输入格式

第一行，22 个整数 SS 和 PP，SS 表示可安装的卫星电话的哨所数，PP 表示边防哨所的数量。

接下里 PP 行，每行两个整数 x，和x，y 描述一个哨所的平面坐标 (x,和)(x，y)，以 km 为单位。

输出格式

第一行，11 个实数 DD，表示无线电收发器的最小传输距离，精确到小数点后两位。

输入输出样例

输入 #1复制

2 4 0 100 0 300 0 600 150 750

输出 #1复制

212.13

说明/提示

数据范围及约定

对于 %P==1

20%

20

的数据：

P=2，S=1

2，秒

；
对于另外 %P==2

20%

20

的数据：

P=4，S=2

4，秒

；
对于 %S<

100%

100

的数据保证：

1≤S≤100

1≤

S≤

100

，

S<P≤500

P≤

500

，

0≤x,和≤10000

0≤

x，y≤

100 00 0

。

**第一次错误原因：**没有仔细审题，题目中要求的是每一对哨所之间直接或间接的至少有一条通话路径，而不是在所有通话路径中寻找倒数最小的几个

源代码：

#include<iostream>
#include<cmath>
using namespace std;
double dist[200005];
int x[505], y[505];
double dist_t(int x1,int x2,int y1,int y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int sy(double s[], double x,int n) {for (int i = 0; i < n; i++) {if (x == s[i])return 0;}return 1;
}
int main() {int s, p;cin >> s >> p;for (int i = 1; i <= p; i++) {cin >> x[i] >> y[i];}int k = 0;for (int i = 1; i <= p; i++) {for (int j = 1; j <= p; j++) {if (i != j)dist[k++] = dist_t(x[i], x[j], y[i], y[j]);}}double min_S[105];int u = 0;while (s--) {double mins = 1e9;for (int i = 0; i < k; i++) {if (dist[i] < mins&&sy(min_S,dist[i],u))mins = dist[i];}min_S[u++] = mins;}printf("%.2lf ", min_S[u - 1]);return 0;
}

**思路：**用最小生成树先将所有的哨点连接起来再根据哨所的距离配备无线电收发器，然后将路径存入一个数组中，进行排序，数组的第k-s个数就是结果

源代码：

#include<iostream>
#include<cmath>
using namespace std;
double dist[505];
double g[505][505];
int x[505], y[505];
double mins[505];
bool vis[505];
int s, p, k = 0;
double dist_t(int x1, int x2, int y1, int y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double min(double a, double b) {if (a > b)return b;elsereturn a;
}
void prim() {dist[1] = 0;for (int i = 1; i <= p; i++) {int t = -1;for (int j = 1; j <= p; j++) {if (!vis[j] && (t == -1 || dist[t] > dist[j]))t = j;}vis[t] = 1;mins[k++] = dist[t];for (int j = 1; j <= p; j++)dist[j] = min(g[t][j], dist[j]);}
}
void insert(double a[], int n) {for (int i = 1; i < n; i++) {double key = a[i];int j = i - 1;while (j>=0&&key<a[j]) {a[j + 1] = a[j];j--;}a[j + 1] = key;}
}
int main() {cin >> s >> p;for (int i = 1; i <= p; i++) {cin >> x[i] >> y[i];}for (int i = 1; i < 505; i++) {dist[i] = 1e9;for (int j = 1; j < 505; j++) {g[i][j] = 1e9;}}for (int i = 1; i <= p; i++) {for (int j = 1; j <= p; j++) {if (i != j)g[i][j]=g[j][i] = min(dist_t(x[i], x[j], y[i], y[j]),g[i][j]);}}prim();insert(mins, k);printf("%.2lf", mins[k - s]);return 0;
}

题目背景

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

题目描述

会场上有 nn 个关键区域，不同的关键区域由 mm 条无向地毯彼此连接。每条地毯可由三个整数 uu、vv、ww 表示，其中 uu 和 vv 为地毯连接的两个关键区域编号，ww 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留至多 KK 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这至多 KK 条地毯的美丽度之和最大为多少。

输入格式

第一行包含三个正整数 nn、mm、KK。

接下来 mm 行中每行包含三个正整数 uu、vv、ww。

输出格式

只包含一个正整数，表示这 KK 条地毯的美丽度之和的最大值。

输入输出样例

输入 #1复制

5 4 3 1 2 10 1 3 9 2 3 7 4 5 3

输出 #1复制

22

说明/提示

选择第 11、22、44 条地毯，美丽度之和为 10+9+3=2210+9+3=22。

若选择第 11、22、33 条地毯，虽然美丽度之和可以达到 10+9+7=2610+9+7=26，但这将导致关键区域 11、22、33 构成一个环，这是题目中不允许的。

1≤n,m,k≤1051≤n,m,k≤105。

**第一次错误原因：**使用插入排序时间复杂度平均情况为O（n2），并且使用嵌套循环导致时间复杂度较高

源代码：

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m, k;
int nexta[N];
int ans = 0;
struct dists {int u, v, w;
}dist[N];
void insert(dists a[], int n) {for (int i = 1; i < n; i++) {dists key = a[i];int j = i - 1;while (j >= 0 && a[j].w < key.w) {a[j+1] = a[j];j--;}a[j + 1] = key;}
}
int find(int x) {if (x != nexta[x]) {return nexta[x] = find(nexta[x]);}return nexta[x];
}
void Union(int x,int y) {int fx = find(x);int fy = find(y);if (fx != fy) {nexta[fy] = fx;}
}
int main() {cin >> n >> m >> k;for (int i = 0; i < N; i++)nexta[i] = i;for (int i = 1; i <= m; i++)cin >> dist[i].u >> dist[i].v >> dist[i].w;insert(dist+1, m);while (k--) {for (int i = 0; i <= m; i++) {if (find(dist[i].u) != find(dist[i].v)) {Union(dist[i].u, dist[i].v);ans += dist[i].w;break;}}}cout << ans;return 0;
}

实际上并不需要使用嵌套循环，只需要用条件控制循环的结束即可，再将排序改成快速排序就可以解决

**思路：**使用并查集和快速排序计算美丽度的和，将u，v，w放在一个结构体中，方便操作，只需要一个i就可以访问对应的三个值，判断是否相连，如果不相连就加上美丽度，再连起来

源代码：

#include<iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, m, k;
int nexta[N];
int ans = 0;
struct dists {int u, v, w;
}dist[N];
bool cmp(dists x, dists y) {return x.w > y.w;
}
int find(int x) {if (x != nexta[x]) {return nexta[x] = find(nexta[x]);}return nexta[x];
}
void Union(int x,int y) {int fx = find(x);int fy = find(y);if (fx != fy) {nexta[fy] = fx;}
}
int main() {cin >> n >> m >> k;for (int i = 0; i < N; i++)nexta[i] = i;for (int i = 1; i <= m; i++)cin >> dist[i].u >> dist[i].v >> dist[i].w;sort(dist + 1, dist + 1 + m, cmp);for (int i = 0; i <= m; i++) {if (find(dist[i].u) != find(dist[i].v)) {Union(dist[i].u, dist[i].v);k--;ans += dist[i].w;if (k == 0)break;}}cout << ans;return 0;
}

题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 tt 区，而自己在 ss 区。

该市有 mm 条大道连接 nn 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 ss 至 tt 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 nn，mm，ss，tt，其含义见【题目描述】。

接下来 mm 行，每行三个整数 u,v,wu,v,w，表示有一条大道连接区 uu 和区 vv，且拥挤度为 ww。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

输入输出样例

输入 #1复制

3 3 1 3 1 2 2 2 3 1 1 3 3

输出 #1复制

2

说明/提示

数据规模与约定

对于 30% 的数据，保证 n≤10。

30%

n≤10
对于 60% 的数据，保证 n≤100。

60%

n≤100
对于 100% 的数据，保证 1≤n≤104，1≤m≤2×104，w≤104，1≤s,t≤n。且从 s 出发一定能到达 t 区。

100%

1≤n≤104

1≤m≤2×104

w≤104

1≤s,t≤n

s

t

样例输入输出 1 解释

小明的妈妈要从 11 号点去 33 号点，最优路线为 11->22->33。

**第一次错误：**低级错误终止条件写错了

源代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 2 * 1e4 + 5;
struct dists {int u, v, w;
}dist[M];
int NEXT[M];
int n, m, s, t;
bool cmp(dists x, dists y) {return x.w < y.w;
}
int find(int x) {if (x != NEXT[x])return NEXT[x] = find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy)NEXT[fy] = fx;
}
int main() {cin >> n >> m >> s >> t;for (int i = 0; i < M; i++) {NEXT[i] = i;}for (int i = 1; i <= m; i++) {cin >> dist[i].u >> dist[i].v >> dist[i].w;}int MAX_s = 0;sort(dist + 1, dist + 1 + m, cmp);for (int i = 1; i <= m; i++) {if (find(dist[i].u) != find(dist[i].v)) {Union(dist[i].u, dist[i].v);MAX_s = max(MAX_s, dist[i].w);}if (find(i) == find(t)) {cout << MAX_s << endl;break;}}return 0;
}

**思路：**从起点开始找，到联通的点的最小拥挤度，一直找到终点为止，再找的过程中不断更新经过的地方的拥挤度的最大值

源代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 2 * 1e4 + 5;
struct dists {int u, v, w;
}dist[M];
int NEXT[M];
int n, m, s, t;
bool cmp(dists x, dists y) {return x.w < y.w;
}
int find(int x) {if (x != NEXT[x])return NEXT[x] = find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy)NEXT[fy] = fx;
}
int main() {cin >> n >> m >> s >> t;for (int i = 0; i < M; i++) {NEXT[i] = i;}for (int i = 1; i <= m; i++) {cin >> dist[i].u >> dist[i].v >> dist[i].w;}int MAX_s = 0;sort(dist + 1, dist + 1 + m, cmp);for (int i = 1; i <= m; i++) {if (find(dist[i].u) != find(dist[i].v)) {Union(dist[i].u, dist[i].v);MAX_s = max(MAX_s, dist[i].w);}if (find(s) == find(t)) {cout << MAX_s << endl;break;}}return 0;
}

第一次错误时并没有立即发现是终止条件错误而导致的错误，于是又写了一个prim算法的

**prim做法的第一次错误：**使用邻接矩阵，导致空间复杂度过高

**思路：**选择s为起点开始找连通的点的最小拥挤度，不断更新最大值，直到p==s时就说明到达终点就可以退出循环。

源代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 2 * 1e4 + 5;
int n, m, s, t;
int dist[M], g[M][M];
bool vis[M];
int prim() {dist[s] = 0;int MAX_min = 0;for (int i = 1; i <= m; i++) {int p = -1;for (int j = 1; j <= m; j++) {if (!vis[j] && (p == -1 || dist[p] > dist[j]))p = j;}if (dist[p] == 1e9)return 1e9;vis[p] = 1;MAX_min = max(MAX_min, dist[p]);if (p == t)return MAX_min;for (int j = 1; j <= m; j++)dist[j] = min(dist[j], g[p][j]);}
}
int main() {cin >> n >> m >> s >> t;for (int i = 1; i <= m; i++) {dist[i] = 1e9;for (int j = 1; j <= m; j++) {g[i][j] = 1e9;}}for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;g[u][v] = g[v][u] = min(g[u][v], w);}int y = prim();cout << y;return 0;
}

正确写法应该改成使用邻接表。邻接表还不会明天再写邻接表的写法

题目描述

输入格式

输出格式

输入输出样例

说明/提示

题目描述

输入格式

输出格式

输入输出样例

说明/提示

数据范围及约定

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

数据规模与约定

样例输入输出 1 解释

相关文章：