Out of Hay.(POJ-2395)
来源：程序员人生 发布时间：2015-05-05 08:11:16 阅读次数：2565次
最小生成树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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
