好贷网好贷款

AOJ - 2224 Save your cat (最大生成树,Kruskal)

发布时间:2016-12-3 12:38:23 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"AOJ - 2224 Save your cat (最大生成树,Kruskal)",主要涉及到AOJ - 2224 Save your cat (最大生成树,Kruskal)方面的内容,对于AOJ - 2224 Save your cat (最大生成树,Kruskal)感兴趣的同学可以参考一下。

传送门 题意:给出一个图,每个环内至少有1只猫,问要砍掉那些边,使得所有的猫获救(无环),而这些边的总长最小。 图中可能不止一棵树。 只要找出最大生成树,那么剩下的就是边长最小的了。 本来想先算出最大生成树的和,在用总的减去它就能算出答案了, 不过想想,直接求也是可以的:ans += 同一连通变量的边(比较短的边)。 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; int N, M; const int MAXN = 10001, MAXM = MAXN*MAXN/2; struct P { int x, y; }p[MAXN]; struct Edge { int u, v; double w; bool operator<(const Edge e)const {return this->w > e.w;} }edge[MAXM]; inline double getdist(P p1, P p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));} int pa[MAXN]; inline int find(int x){return pa[x] == x ? x : pa[x] = find(pa[x]);} double Kruskal() { double ans = 0; for(int i = 1; i <= N; i++) pa[i] = i; sort(edge, edge+M); for(int i = 0; i < M; i++) { Edge e = edge[i]; int x = find(e.u), y = find(e.v); if(x != y) pa[x] = y; else ans += e.w; } return ans; } int main() { //freopen("in.txt", "r", stdin); scanf("%d%d", &N, &M); double ans = 0; for(int i = 1; i <= N; i++) scanf("%d%d", &p[i].x, &p[i].y); for(int i = 0; i < M; i++) { scanf("%d%d", &edge[i].u, &edge[i].v); edge[i].w = getdist(p[edge[i].u], p[edge[i].v]); } ans = Kruskal(); printf("%.3f\n", ans); return 0; }

上一篇:Android搭建开发环境
下一篇:我的Java学习--对c语言的了解

相关文章

相关评论