题目大意：给出N个点。M条边。问这N个点形成的生成树的最大权值边-最小权值边的最小值
解题思路：先排序，然后按生成树的kruscal算法进行加边，再维护一个最小权值边
加边的时候要考虑一下加下去的边是否会形成环，假设形成环的话，就把环内的最小边去掉，然后再找出这棵新的生成树的最小边等到生成树形成的时候，由于加入进去的新边的权值肯定是最大值的，所以仅仅要仅仅减去之前维护一个的最小值就能够了
#include#include #include #include using namespace std;#define N 400#define M 160010#define INF 0x3f3f3f3fstruct Edge{ int u, v, c; Edge() {} Edge(int u, int v, int c): u(u), v(v), c(c) {}}E[M];int f[N], dis[N][N];int cnt, Min_Edge, n, m;bool vis[N];int cmp(const Edge &a, const Edge &b) { return a.c < b.c;}void init() { for (int i = 0; i < m; i++) { scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].c); dis[E[i].u][E[i].v] = dis[E[i].v][E[i].u] = E[i].c; }}int LCA(int i) { int u = E[i].u, v = E[i].v, c = E[i].c; memset(vis, 0, sizeof(vis)); while (!vis[u]) { vis[u] = true; if (u == f[u]) break; u = f[u]; } while (!vis[v] && f[v] != v) v = f[v]; if (!vis[v]) return -1; return v;}void findCycle(int i) { int lca = LCA(i); if (lca == -1) return ; int u = E[i].u, v = E[i].v, c = E[i].c; Edge MinEdge; MinEdge.c = INF; int fu = f[u]; while (fu != u && u != lca) { if (dis[fu][u] < MinEdge.c) MinEdge = Edge(fu, u, dis[fu][u]); fu = f[fu]; u = f[u]; } int fv = f[v]; while (fv != v && v != lca) { if (dis[fv][v] < MinEdge.c) MinEdge = Edge(fv, v, dis[fv][v]); fv = f[fv]; v = f[v]; } f[MinEdge.v] = MinEdge.v; Min_Edge = INF; for (int i = 0; i < n; i++) if (f[i] != i && dis[f[i]][i] < Min_Edge) Min_Edge = dis[f[i]][i]; cnt--;}void AddEdge(int i) { int u = E[i].u, v = E[i].v, c = E[i].c; if (f[u] == u) f[u] = v; else if (f[v] == v) f[v] = u; else { vector vec; while (1) { vec.push_back(u); if (u == f[u]) break; u = f[u]; } int size = vec.size(); for (int i = size - 1; i > 0; i--) f[vec[i]] = vec[i - 1]; f[E[i].u] = E[i].v; } Min_Edge = min(Min_Edge, c); cnt++;}void solve() { sort(E, E + m, cmp); for (int i = 0; i < n; i++) f[i] = i; int ans = INF; Min_Edge = INF; cnt = 0; for (int i = 0; i < m; i++) { findCycle(i); AddEdge(i); if (cnt == n - 1) ans = min(ans, E[i].c - Min_Edge); } printf("%d\n", ans);}int main() { while (scanf("%d", &n) != EOF && n) { scanf("%d", &m); init(); solve(); } return 0;}