Out of Hay.(POJ-2395)

最小生成树kruskal算法。

首先必须构成1棵最小生成树,然后找出最长的路。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int n,m,a,b,c,par[1005],rankk[1005], max_road;
struct edge {
int u,v,cost;
edge(int u=0,int v=0,int cost=0) : u(u),v(v),cost(cost) {}
};
bool cmp(const edge& e1,const edge& e2) {
return e1.cost<e2.cost;
}
edge es[20005];
void init(int n) {
for(int i=1;i<=n;i++) {
par[i] = i;
rankk[i] = 0;
}
}
int findd(int x) {
return par[x] == x ? x : par[x] = findd(par[x]);
}
void unite(int x,int y) {
x = findd(x);
y = findd(y);
if(x==y) return ;
if(rankk[x] < rankk[y]) {
par[x] = y;
} else {
par[y] = x;
if(rankk[x] == rankk[y]) rankk[x] ++ ;
}
}
bool same(int x,int y) {
return findd(x) == findd(y);
}
int kruskal() {
sort(es,es+m,cmp);
init(n);
int res = 0;
for(int i=0;i<m;i++) {
edge e = edge(es[i].u,es[i].v,es[i].cost);
if(!same(e.u,e.v)) {
unite(e.u,e.v);
res += e.cost;
max_road = max(max_road,e.cost);
}
}
return res;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) {
scanf("%d%d%d",&a,&b,&c);
es[i] = edge(a,b,c);
}
max_road = ⑴;
int sum = kruskal();
printf("%d
",max_road);
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Out of Hay.(POJ-2395)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡