POJ_3522
这个题目我们可以枚举每条边作为生成树中权值最小的边，然后做最小生成树，不过我们这样去写，不知道会不会超时。
也可以在做kruscal的时候，如果加上当前边会构成环，那么就将这个环上权值最小的边删掉。同时如果当前已经形成了最小生成树，就遍历一遍生成树，找到边权的最大值和最小值更新一下结果。
#include#include #include #define MAXD 110#define MAXM 10010#define INF 0x3f3f3f3fusing namespace std;int N, M, first[MAXD], e, pre[MAXM], next[MAXM], u[MAXM], v[MAXM], w[MAXM], p[MAXD];struct Edge{ int u, v, w; bool operator < (const Edge &t) const { return w < t.w; }}edge[MAXM];int Find(int x){ return p[x] == x ? x : (p[x] = Find(p[x]));}void init(){ int i; for(i = 0; i < M; i ++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); sort(edge, edge + M);}void add(int x, int y, int z){ u[e] = x, v[e] = y, w[e] = z; if(first[x] != -1) pre[first[x]] = e; pre[e] = -1; next[e] = first[x], first[x] = e ++;}void Delete(int k){ if(pre[k] == -1) first[u[k]] = next[k]; else next[pre[k]] = next[k]; if(next[k] != -1) pre[next[k]] = pre[k];}void dfs(int cur, int fa, int to, int m, int k){ if(cur == to) { Delete(k), Delete(k ^ 1); return ; } int i; for(i = first[cur]; i != -1; i = next[i]) if(v[i] != fa) { if(w[i] < m) dfs(v[i], cur, to, w[i], i); else dfs(v[i], cur, to, m, k); }}void Search(int cur, int fa, int &min, int &max){ int i; for(i = first[cur]; i != -1; i = next[i]) { if(v[i] != fa) { if(w[i] < min) min = w[i]; if(w[i] > max) max = w[i]; Search(v[i], cur, min, max); } }}void solve(){ int i, j, k, tx, ty, cnt = 0, ans = INF, min, max; for(i = 1; i <= N; i ++) p[i] = i; memset(first, -1, sizeof(first)); e = 0; for(i = 0; i < M; i ++) { tx = Find(edge[i].u), ty = Find(edge[i].v); if(tx != ty) ++ cnt, p[ty] = tx; else dfs(edge[i].u, -1, edge[i].v, INF, 0); add(edge[i].u, edge[i].v, edge[i].w), add(edge[i].v, edge[i].u, edge[i].w); if(cnt == N - 1) { min = INF, max = 0; Search(1, -1, min, max); if(max - min < ans) ans = max - min; } } if(cnt != N - 1) printf("-1\n"); else printf("%d\n", ans);}int main(){ for(;;) { scanf("%d%d", &N, &M); if(!N && !M) break; init(); solve(); } return 0;}