练习题(2025.2.9)

题目背景

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

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 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。

接上昨天邻接表的写法

kruskal的做法在昨天的总结中

源代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int M = 2e4 + 5;
int n, m, s, t;
int dist[M];
bool vis[M];
vector<pair<int, int>> g[M];
int prim() {for (int i = 1; i <= m; i++) {dist[i] = 1e9;}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 (const auto& edge : g[p]) {int to = edge.first;int w = edge.second;dist[to] = min(dist[to], w);}}return -1;
}
int main() {cin >> n >> m >> s >> t;for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;g[u].emplace_back(v, w);g[v].emplace_back(u, w);}int y = prim();cout << y;return 0;
}

题目描述

又到了一年一度的明明生日了，明明想要买 BB 样东西，巧的是，这 BB 样东西价格都是 AA 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 II 样东西，再买第 JJ 样，那么就可以只花 KI,JKI,J 元，更巧的是，KI,JKI,J 竟然等于 KJ,IKJ,I。

现在明明想知道，他最少要花多少钱。

输入格式

第一行两个整数，A,BA,B。

接下来 BB 行，每行 BB 个数，第 II 行第 JJ 个为 KI,JKI,J。

我们保证 KI,J=KJ,IKI,J=KJ,I 并且 KI,I=0KI,I=0。

特别的，如果 KI,J=0KI,J=0，那么表示这两样东西之间不会导致优惠。

注意 KI,JKI,J 可能大于 AA。

输出格式

一个整数，为最小要花的钱数。

输入输出样例

输入 #1复制

1 1 0

输出 #1复制

1

输入 #2复制

3 3 0 2 4 2 0 2 4 2 0

输出 #2复制

7

说明/提示

样例解释 22。

先买第 22 样东西，花费 33 元，接下来因为优惠，买 1,31,3 样都只要 22 元，共 77 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 44 元买剩下那件，而选择用 22 元。）

数据规模

对于 30%30% 的数据，1≤B≤101≤B≤10。

对于 100%100% 的数据，1≤B≤500,0≤A,KI,J≤10001≤B≤500,0≤A,KI,J≤1000。

2018.7.25新添数据一组

思路：把价格看成边权，位置看成点

源代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int B = 505;
struct dists {int u, v, w;
}dist[B * B];
int a, b, k = 0, u = 0;
int NEXT[B * B];
int ans = 0;
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;
}
bool cmp(const dists x, const dists y) {return x.w < y.w;
}
int main() {cin >> a >> b;for (int i = 0; i < B*B; i++)NEXT[i] = i;for (int i = 1; i <= b; i++) {for (int j = 1; j <= b; j++) {cin >> dist[++k].w;dist[k].u = i;dist[k].v = j;if (dist[k].w == 0)dist[k].w = a;}}sort(dist + 1, dist + k + 1, cmp);ans += a;for (int i = 1; i <= k; i++) {if (find(dist[i].u) != find(dist[i].v)) {Union(dist[i].u, dist[i].v);if (dist[i].w < a)ans += dist[i].w;elseans += a;b--;if (b == 0)break;}}cout << ans;return 0;
}

 

问题描述

有一个 SNS 被 NN 个用户使用，他们的编号从 11 到 NN。

在这个 SNS 中，两个用户可以成为朋友。

友谊是双向的；如果用户 X 是用户 Y 的朋友，那么用户 Y 也一定是用户 X 的朋友。

目前，在 SNS 上有 MM 对朋友关系，第 ii 对由用户 AiAi 和用户 BiBi 组成。

确定可以执行以下操作的最大次数：

• 操作：选择三个用户 X、Y 和 Z，使得 X 和 Y 是朋友，Y 和 Z 是朋友，但 X 和 Z 不是朋友。让 X 和 Z 成为朋友。

约束条件

• 2≤N≤2×1052≤N≤2×105

• 0≤M≤2×1050≤M≤2×105

• 1≤Ai<Bi≤N1≤Ai<Bi≤N

• 这些对  是不同的。

  (Ai,Bi)(Ai,Bi)

• 所有输入值都是整数。

输入

输入以以下格式从标准输入给出：

NNMMA1A1B1B1⋮⋮AMAMBMBM

输出

输出答案。

示例 1

Inputcopy	Outputcopy
`4 3
1 2
2 3
1 4`	3

可以发生三次新的朋友关系，方法如下：

• 用户  和他们的朋友（用户 ）的朋友（用户 ）成为朋友

  11

  22

  33

• 用户  和他们的朋友（用户 ）的朋友（用户 ）成为朋友

  33

  11

  44

• 用户  和他们的朋友（用户 ）的朋友（用户 ）成为朋友

  22

  11

  44

不会有四次或更多的新朋友关系。

示例 2

Inputcopy	Outputcopy
3 0	0

如果没有初始的朋友关系，就不会发生新的朋友关系。

示例 3

Inputcopy	Outputcopy
`10 8
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10`	12

错误代码：不知道错哪了求大佬教一教QWQ

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 2e5 + 5;
int NEXT[M];
int vis[M], bj[M];
int n, m, u, v;
int ans = 0;
int val[1000];
int find(int x) {if (x != NEXT[x])return NEXT[x] = find(NEXT[x]);return NEXT[x];
}
void Union(int x, int y) {if (find(x) != find(y))NEXT[find(y)] = find(x);
}
int sy(int a[], int x,int n) {for (int i = 0; i < n; i++) {if (a[i] == x)return 1;}return 0;
}
int main() {cin >> n >> m;for (int i = 0; i <= n; i++)NEXT[i] = i;for (int i = 1; i <= m; i++) {cin >>u >> v;Union(u, v);}for (int i = 1; i <= n; i++)vis[i] = find(i);int k = 1;for (int i = 1; i <= n; i++) {if (!sy(bj, vis[i], k)) {val[k - 1] = i - 1;bj[k++] = vis[i];}}val[k-1] = n;for (int i = 0; i < k - 1; i++) {int c = val[i + 1] - val[i];ans += c * (c - 1) / 2;}cout << ans - m;return 0;
}