題目鏈接：10048 - Audiophobia

題目大意：有n個城市，和m條街道，每條街道有一個噪音值，q次去問，從城市a到城市b，路徑上分貝值的最大值最小為多少。

解題思路：與uva 10099的做法是一樣的，可以參考一下。

?

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 105; const int M = 1005; const int Q = 10005; struct state {int r, l, num; }s[M]; int n, m, f[N];int getfather(int x) {return x == f[x] ? x : f[x] = getfather(f[x]); }bool cmp(const state& a, const state& b) {return a.num < b.num; }void init() {for (int i = 0; i < m; i++)scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].num);sort(s, s + m, cmp); }int kruskal() {int a, b;scanf("%d%d", &a, &b);for (int i = 1; i <= n; i++)f[i] = i;for (int i = 0; i < m; i++) {int p = getfather(s[i].l), q = getfather(s[i].r);if (p != q) {f[p] = q;if (getfather(a) == getfather(b))return s[i].num;}}return -1; }int main () {int cas = 0, q;while (scanf("%d%d%d", &n, &m, &q), n || m || q) {init();if (cas) printf("\n");printf("Case #%d\n", ++cas);for (int i = 0; i < q; i++) {int ans = kruskal();if (ans < 0)printf("no path\n");elseprintf("%d\n", ans);}}return 0; }

?

?

轉載于:https://www.cnblogs.com/james1207/p/3366199.html

總結

以上是生活随笔為你收集整理的uva 10048 Audiophobia(最小生成树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。