POJ 3522 Slim Span

2019-11-14 12:04:41

字体：大中小

来源：转载

供稿：网友

2017寒假集训 3-G

POJ 3522 Slim Span

kruskal生成树

传送门：HUSTOJ

传送门：POJ

题意

图，求生成树，使得树内最大权边与最小权边差最小。

思路

又是一道以前看过没写的题。。不过这题比较简单，就当是留一下kruskal的板子。

要求生成树最大权最小权差最小，那么边要先排序，就想到了kruskal。kruskal选取方式是贪心，所以最小边确定了后最大边必然确定，而kruskal选出来的那个最大边的权一定会尽可能的小。

到现在思路就很明确了，枚举最小边。判断剩下的边能不能成为生成树，如果能，记录第一条加入的边与第n-1条加入的边(对应最大权边与最小权边)权差。

代码

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>using namespace std;const int MAXN=107;const int MAXM=5007;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;int father[MAXN];void init(int n){ for(int i=1; i<=n; i++) { father[i]=i; }}int find(int x){ if(father[x]==x) return x; else { return father[x]=find(father[x]); }}void merge(int x, int y){ int fx=father[x], fy=father[y]; if(fx!=fy) father[fx]=fy;}struct edge{ int from, to, cost; edge(){} edge(int a, int b, int c){ from=a;to=b;cost=c; }};bool cmp(edge a, edge b){ return a.cost<b.cost;}edge e[MAXM];int main(){ int n, m; while(cin>>n>>m&&(n!=0)) { memset(e, 0, sizeof(e)); for(int i=0;i<m;i++) { scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].cost); } sort(e, e+m,cmp); int res=oo; for(int i=0;i<=m-n+1;i++) { int tres=e[i].cost; init(n+1); int cnt=0; for(int j=i;j<m;j++) { edge te=e[j]; if(find(te.from)!=find(te.to)) { merge(te.from, te.to); cnt++; } if(cnt==n-1) { tres=e[j].cost-tres; break; } } if(cnt==n-1) res=min(res, tres); } cout<<(res>=oo ? -1 : res)<<endl; } //system("pause"); return 0;}

上一篇：黄金分割数

下一篇：Java_静态方法中调用非静态方法

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注