UVA 10457 Magic Car——最小瓶颈路

UVA 10457 Magic Car——最小瓶颈路

其实就是瞎搞， 二重循环，第一层枚举最小值，第二层从最小值开始跑MST，当起点和终点在一个集合中时停止，此时求得的边权就是最大值，然后更新结果就好了

PS：第一次刷到vjudge时间第一

#include #include #include #include using namespace std;const int maxn = 205;const int maxm = 1005;const int INF = 0x3f3f3f3f;int n, m, scost, ecost, q, s, e, ans;struct Edge { int from, to, cost; bool operator < (const Edge &temp) const { return cost < temp.cost; }}edge[maxm];int fa[maxn], ran[maxn];void init(int x) { for (int i = 0; i <= x; i++) fa[i] = i, ran[i] = 0;}int query(int x) { return fa[x] == x ? x : fa[x] = query(fa[x]); }inline void unite(int x, int y) { x = query(x), y = query(y); if (x == y) return; if (ran[x] < ran[y]) fa[x] = y; else { fa[y] = x; if (ran[x] == ran[y]) ran[x]++; }}int main() { while (~scanf("%d %d", &n, &m)) { for (int i = 1; i <= m; i++) scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].cost); sort(edge + 1, edge + 1 + m); scanf("%d %d %d", &scost, &ecost, &q); while (q--) { ans = INF; scanf("%d %d", &s, &e); for (int i = 1; i <= m; i++) { init(n); for (int j = i; j <= m; j++) { if (edge[j].cost - edge[i].cost + scost + ecost >= ans) break; unite(edge[j].from, edge[j].to); if (query(s) == query(e)) { ans = min(ans, edge[j].cost - edge[i].cost + scost + ecost); break; } } } printf("%d\n", ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。