UVA1395 Slim Span

梦里梦外; 2022-05-16 08:42 153阅读 0赞

题目链接：[点我][Link 1]  
题意简述

求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

并查集生成最小生成树，将边按从小到大排序，生成一个树更新一下答案

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 100 + 10;
    const int INF = 0x3f3f3f3f;
    int n;
    int pa[maxn];
    
    int find(int x){
    	if(x!=pa[x]){
    		return pa[x]=find(pa[x]);
    	}
    	else{
    		return x;
    	}
    }
    struct Edge {
      int u, v, d;
      Edge(int u, int v, int d):u(u),v(v),d(d) {}
      bool operator < (const Edge& rhs) const {
        return d < rhs.d;
      }
    };
    
    vector<Edge> e;
    
    int solve() {
      int m = e.size();
      sort(e.begin(), e.end());
      int ans = INF;
      for(int L = 0; L < m; L++) {
        for(int i = 1; i <= n; i++) pa[i] = i;
        int cnt = n; // number of sets
        for(int R = L; R < m; R++) {
          int u = find(e[R].u), v = find(e[R].v);
          if(u != v) {
            pa[u] = v;
            if(--cnt == 1) { ans = min(ans, e[R].d-e[L].d); break; }
          }
        }
      }
      if(ans == INF) ans = -1;
      return ans;
    }
    
    int main() {
      int m, u, v, d;
      while(scanf("%d%d", &n, &m) == 2 && n) {
        e.clear();
        for(int i = 0; i < m; i++) {
          scanf("%d%d%d", &u, &v, &d);
          e.push_back(Edge(u, v, d));
        }
        printf("%d\n", solve());
      }
      return 0;
    }

[Link 1]: https://www.luogu.org/problemnew/show/UVA1395

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 1395 Slim Span--苗条的生成树（并查集+枚举）

题意：给出n(n<=100)个结点的图，求苗条度（最大边减最小边的值）尽量小的生成树。数据量最大为5000，枚举遍历，复杂度m^2。 AC代码： include

痛定思痛。/ 2024年02月17日 22:09/ 0 赞/ 42 阅读

相关 php slim 教程,PHP框架slim的安装使用方法

最简单粗暴和直接的方法——到github下载zip文件，slim github【链接】。解压之后把【1】Slim文件夹，【2】.htaccess文件和【3】index.php文

曾经终败给现在/ 2022年10月22日 04:26/ 0 赞/ 255 阅读

相关 HDU 1395(欧拉定理)

欧拉φ函数的值　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0

绝地灬酷狼/ 2022年09月20日 12:49/ 0 赞/ 182 阅读

相关 POJ 3522-Slim Span（苗条树-kruskal生成树）

Slim Span <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000MS</t

向右看齐/ 2022年06月16日 03:22/ 0 赞/ 165 阅读

相关 Slim Span UVA - 1395 ——Kruskal算法生成最小树

Think: 1Kruskal算法生成最小树 2题意理解: 1>生成一颗最小树使得他的边的最大权值减去边的最小权值最小 3思路:从权值最小的边出发建立最小生成树

待我称王封你为后i/ 2022年06月15日 06:57/ 0 赞/ 130 阅读

相关 Slim Span

题目链接：[https://vjudge.net/contest/179332\problem/H][https_vjudge.net_contest_179332_probl

「爱情、让人受尽委屈。」/ 2022年06月10日 11:53/ 0 赞/ 146 阅读

相关 POJ 3522 Slim Span（生成树+克鲁斯卡尔）

Given an undirected weighted graph G, you should find one of spanning trees specified as

女爷i/ 2022年06月10日 02:52/ 0 赞/ 149 阅读

相关 poj-3522-Slim Span

Slim Span <table> <tbody> <tr> <td><strong>Time Limit:</strong> 5000MS

爱被打了一巴掌/ 2022年05月20日 08:53/ 0 赞/ 127 阅读

相关 UVA1395 Slim Span

题目链接：[点我][Link 1] 题意简述求所有生成树中最大边权与最小边权差最小的，输出它们的差值。并查集生成最小生成树，将边按从小到大排序，生成一个树更新一下答

梦里梦外;/ 2022年05月16日 08:42/ 0 赞/ 154 阅读

相关 TensorFlow (五): Slim

Slim Slim 简介代码对比原生 TensorFlow Slim 共享参数 Slim 简介 Slim ( tf

谁践踏了优雅/ 2022年03月14日 15:52/ 0 赞/ 245 阅读