学步园

最瘦生成树

即求生成树中最大边和最小边差值最小

/*<br /> * File: PKU 3522 Slim Span<br /> * Author: xiaotian @ hnu<br /> * Created on 2010年10月8日, 上午11:10<br /> * 题解：最瘦生成树<br /> */<br /> #include<stdio.h><br /> #include<iostream><br /> #include<string.h><br /> #include<queue><br /> #include<map><br /> #include<set><br /> #include<math.h><br /> using namespace std;<br /> #define N 108<br /> #define E 5008<br /> #define inf 0x7ffffff<br /> int fat[N];<br /> int rank[N];<br /> int n, m;<br /> struct node {<br /> int x, y, len;<br /> node(int a = 0, int b = 0, int c = 0) : x(a), y(b), len(c) {}<br /> bool operator<(const node & r)const { /* 这里决定是最大还是最小生成树 */<br /> return len < r.len; /* 大于号就是最大生成树，小于号就是最小生成树 */<br /> }<br /> };<br /> node edge[E];<br /> void build() {<br /> int i, a, b;<br /> int c;<br /> for (i = 0; i < m; i++) {<br /> scanf("%d%d%d", &a, &b, &c);<br /> edge[i] = node(a - 1, b - 1, c);<br /> }<br /> sort(edge, edge + m);<br /> }<br /> void Make_set() {<br /> for (int i = 0; i < n; i++) {<br /> fat[i] = i;<br /> rank[i] = 0;<br /> }<br /> }<br /> int Find_set(int x) {<br /> if (x != fat[x]) fat[x] = Find_set(fat[x]);<br /> return fat[x];<br /> }<br /> int Union(int k) {<br /> int x, y;<br /> x = Find_set(edge[k].x);<br /> y = Find_set(edge[k].y);<br /> if (x == y) return 0;<br /> if (rank[x] > rank[y]) fat[y] = x;<br /> else {<br /> if (rank[x] == rank[y]) rank[y]++;<br /> fat[x] = y;<br /> }<br /> return edge[k].len;<br /> }<br /> bool judge() { /* 判断是否连通 */<br /> int i;<br /> for (i = 1; i < n; i++)<br /> if (Find_set(i) != Find_set(i - 1))<br /> return 0;<br /> return 1;<br /> }<br /> int Kruskal(int k) {<br /> int i;<br /> int ans = 0;<br /> Make_set();<br /> for (i = k; i < m; i++) {<br /> int p = Union(i);<br /> if (p) ans = p;<br /> }<br /> if (judge()) return ans - edge[k].len;<br /> else return -1; /* 不连通，不存在生成树 */<br /> }<br /> int main() {<br /> while (scanf("%d%d", &n, &m) != EOF) {<br /> if(n==0 && m==0) return 0;<br /> build();<br /> int ans = Kruskal(0);<br /> if (ans == -1) {<br /> puts("-1");<br /> continue;<br /> }<br /> for (int i = 1; i < m; i++) {<br /> int tmp = Kruskal(i);<br /> if (tmp == -1) break;<br /> if (tmp < ans) ans = tmp;<br /> }<br /> printf("%d/n", ans);<br /> }<br /> return 0;<br /> }