首页 > 代码库 > （极差最小生成树）POJ 3522 - Slim Span
（极差最小生成树）POJ 3522 - Slim Span
题意：
给定一张无向图，求出一个最长边减最短边最小的生成树。
分析：
这题之前做过一模一样的（应该是。。。），跑kruskal算法，维护一个subset，一旦出现了环，就删除这条环上最轻的边，不断更新subset，subset中存当前生成树的边，一旦边的个数m=点数n-1，就更新ans。
这个复杂度是O(m*n)。但是在这里样例都过不去，应该是写搓了。。。鲁棒性不够。
还有一个解法是用动态树link-cut-tree，可以再把复杂度降成O(m*logn)。但是我还不会。。
这题因为点的数量只有100个，直接暴力就行了。
暴力枚举限制最小的边，计算最小生成树即可。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 7 8 using namespace std; 9 10 const int inf = 0x3f3f3f3f;11 const int maxn = 110;12 13 int n, m;14 int par[maxn];15 16 struct Edge {17 int u, v, c;18 bool operator<(const Edge &a)const {19 return c < a.c;20 }21 Edge(int _u, int _v, int _c) {22 u = _u, v = _v, c = _c;23 }24 };25 26 vector<Edge> edge;27 28 int findx(int x) {29 if(par[x] == x)return x;30 else return par[x] = findx(par[x]);31 }32 33 void init() {34 for(int i = 1; i <= n; i++) {35 par[i] = i;36 }37 }38 39 int main() {40 while(~scanf("%d%d", &n, &m)) {41 if(n == 0 && m == 0)break;42 edge.clear();43 for(int i = 0; i < m; i++) {44 int u, v, c;45 scanf("%d%d%d", &u, &v, &c);46 edge.push_back(Edge(u, v, c));47 }48 sort(edge.begin(), edge.end());49 int ans = inf;50 for(int i = 0; i <= m - n + 1; i++) {51 init();52 int cnt = 0;53 for(int j = i; j < m; j++) {54 int t1 = findx(edge[j].u);55 int t2 = findx(edge[j].v);56 if(t1 != t2) {57 par[t1] = t2;58 cnt++;59 }60 if(cnt == n - 1) {61 ans = min(ans, edge[j].c - edge[i].c);62 break;63 }64 }65 }66 if(ans == inf)puts("-1");67 else printf("%d\n", ans);68 }69 return 0;70 71 }
（极差最小生成树）POJ 3522 - Slim Span
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。