c语言实现输入一个 C 个点 S 条边的无向带权图,边权表示该路径上的噪声值。当噪声值太大时,耳膜可能会受到伤害,所以当你从某点去往另一个点时,总是希望路上经过的最大噪声值最小。输入一些询问,每次询问两个点,输出这两个点间「最大噪声值最小的路径」上,噪声值最大的一条边的噪声值。 如果两个点之间不连通,输出 "no path"。(不含引号)
时间: 2023-12-17 14:04:44 浏览: 48
以下是一种实现方式:
```c
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAXN 1005
#define MAXM 100005
int n, m, q;
int head[MAXN], ver[MAXM<<1], nxt[MAXM<<1], w[MAXM<<1], tot = 1;
int vis[MAXN], dis[MAXN];
int st, ed;
inline int max(int a, int b) {
return a > b ? a : b;
}
inline void add(int x, int y, int z) {
ver[++tot] = y, w[tot] = z;
nxt[tot] = head[x], head[x] = tot;
}
inline void init() {
memset(head, 0, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(dis, INF, sizeof(dis));
tot = 1;
}
int dfs(int u, int t, int limit) {
if (u == t) return 1;
vis[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i], cost = w[i];
if (!vis[v] && cost <= limit && dfs(v, t, limit)) return 1;
}
return 0;
}
int check(int mid) {
memset(vis, 0, sizeof(vis));
return dfs(st, ed, mid);
}
int main() {
while (~scanf("%d%d", &n, &m)) {
init();
for (int i = 1, x, y, z; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z), add(y, x, z);
}
scanf("%d", &q);
while (q--) {
scanf("%d%d", &st, &ed);
int l = 0, r = INF, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
if (ans == -1) printf("no path\n");
else printf("%d\n", ans);
}
}
return 0;
}
```
首先,我们用邻接表存储图,然后进行二分答案。对于当前二分的答案(即最大噪声值),我们进行一次 dfs ,判断从起点是否能到达终点,并且路径上的最大噪声值不超过当前二分的答案。如果能到达,则说明当前二分的答案可行,将答案更新为当前噪声值,继续缩小区间;否则,说明当前二分的答案不可行,需要增大噪声值,扩大区间。最终得到的答案即为所求。