锐客网

  1. 首页 > it技术 > >

Slim|Slim Span (最小生成树）

题意

求生成树的最长边与最短边的差值的最小值
题解
最小生成树保证每一条边最小，就只要枚举最小边开始，跑最小生成树，最后一个值便是最大值
在枚举最小边同时维护差值最小，不断更新最小值。
C++代码
/** /*@author Victor /*language C++ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; #define pii pair #define pll pair #define pil pair #define pli pair #define pdl pair #define pld pair #define pdd pair #define iput(n) scanf("%d",&n); #define dput(n) scanf("%lf",&n); #define llput(n) scanf("%lld",&n); #define cput(n) scanf("%s",n); #define puti(n) printf("%d\n",n); #define putll(n) printf("%lld\n",n); #define putd(n) printf("%lfd\n",n); #define _cls(n) memset(n,0,sizeof(n)); //求二进制中1的个数 //__builtin_popcount(n); //求2^k //#define (ll)Pow(2,k) (1LL<Rank[fy]) par[fx]=fy; else { par[fy]=fx; if(Rank[fx]==Rank[fy]) Rank[x]++; } } //关于路径压缩 int find2(int x) { int fx=find(x); int t; while(x!=fx) { t=par[x]; par[x]=fx; x=t; } return fx; }// 最小生成树 Kruskal 算法 int minn; int Kruskal() { minn = 1e9; edge e; int i,res; sort(eg,eg+m,cmp); // 构建最小生成树 for(int j = 0; j < m; j ++){ init(n); res=0; for( i=j; i
【Slim|Slim Span (最小生成树）】
转载于:https://www.cnblogs.com/DWVictor/p/11228659.html

    推荐阅读


    上一篇：POJ|POJ 3522 Slim Span

    下一篇：codeforces|codeforces E. Famil Door and Roads 期望