首页 > 代码库 > UVA 10457 - Magic Car(最小瓶颈路)
UVA 10457 - Magic Car(最小瓶颈路)
UVA 10457 - Magic Car
题目链接
题意:m条路,每条路上必须维持速度v,现在有一辆车,启动能量和结束能量为a, b,途中消耗能量为经过路径最大速度减去最小速度,现在每次循环给定起点终点,问最小能量花费
思路:最小瓶颈路,利用kruskal去搞
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 205; const int M = 1005; int n, m, parent[N]; struct Edge { int u, v, val; bool operator < (const Edge& c) const { return val < c.val; } void read() { scanf("%d%d%d", &u, &v, &val); } } E[M]; int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]); } int solve(int s, int e) { int ans = 1000000000; for (int i = 0; i < m; i++) { for (int j = 1; j <= n; j++) parent[j] = j; for (int j = i; j < m; j++) { int pu = find(E[j].u); int pv = find(E[j].v); if (pu != pv) parent[pu] = pv; if (find(s) == find(e)) { ans = min(ans, E[j].val - E[i].val); break; } } } return ans; } int main() { while (~scanf("%d%d", &n, &m)) { for (int i = 0; i < m; i++) E[i].read(); sort(E, E + m); int a, b, q, u, v; scanf("%d%d", &a, &b); scanf("%d", &q); while (q--) { scanf("%d%d", &u, &v); printf("%d\n", a + b + solve(u, v)); } } return 0; }
UVA 10457 - Magic Car(最小瓶颈路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。