题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1598
思路
用kruskal 算法
将边排序后 跑 kruskal
然后依次将最小边删除 再去跑 kruskal 直到不能成功跑成通路
为什么要删掉最小边 因为边是按从小到大排序的
那么也就是说 我每次加入的边 都是必须加入的 最小的边
那么如果 最高速与最低速的差 还大了
我就要让尽量大的边去跑 kruskal
举个栗子吧。。
假设存在一系列边
1 2 3 4 5 5 7 8 9
排序后是这样的
假如我用 1 2 3 4 5 这五条边 可以跑成通路 这五条边的 最高速-最低速就是 4
那么当我删去1 这条边后 我再去跑 发现 2 3 4 5 5 这五条边也可以跑成通路，那么最高速-最低速就是3
然后发现答案其实是更优的 也存在一点贪心的思想
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 10; const int MOD = 6; int n, m; int pre[maxn]; int st, ed; int find(int x) { while (x != pre[x]) x = pre[x]; return x; } void join(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) pre[fx] = fy; } struct node { int u, v, w; node(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {} bool operator < (const node& r) const { return w < r.w; } }; node edge[maxn]; int tot; void addedge(int u, int v, int w) { edge[tot].u = u; edge[tot].v = v; edge[tot].w = w; tot++; } int Kruskal(int n, int vis) { for (int i = 0; i < n; i++) pre[i] = i; int Min = edge[vis].w; int Max; for (int i = vis; i < tot; i++) { node u = edge[i]; if (find(u.u) != find(u.v)) { join(u.u, u.v); Max = u.w; } if (find(st) == find(ed)) return Max - Min; } return -1; } int main() { while (scanf("%d%d", &n, &m) != EOF) { tot = 0; int u, v, w; for (int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } sort(edge, edge + tot); int q; cin >> q; while (q--) { scanf("%d%d", &st, &ed); int ans = INF; for (int i = 0; i < tot; i++) { int vis = Kruskal(n, i); if (vis == -1) break; ans = min(ans, vis); } printf("%d\n", ans == INF ? -1 : ans); } } }转载于:https://www.cnblogs.com/Dup4/p/9433078.html
相关资源：JAVA上百实例源码以及开源项目