Bad Cowtractors.(POJ-2377)
来源：程序员人生 发布时间：2015-05-29 08:22:35 阅读次数：2724次
最大生成树，只需要变1下改变值的部份就能够了。
尝试了1下应用并查集的kruskal算法，与prim相比各有益弊吧，还要根据数据特点适当选取。
#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];
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;
}
}
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);
}
int sum = kruskal();
bool ok = true;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i!=j) if(!same(i,j)) {
ok = false; break;
}
}
if(!ok) break;
}
if(ok) printf("%d
",sum);
else printf("⑴
");
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
