首页 > 代码库 > POJ1258 Agri-Net MST最小生成树题解
POJ1258 Agri-Net MST最小生成树题解
搭建一个最小代价的网络,最原始的最小生成树的应用。
这里使用Union find和Kruskal算法求解.
注意:
1 给出的数据是原始的矩阵图,但是需要转化为边表示的图,方便运用Kruskal,因为需要sort
2 减少边,一个矩阵最多需要(N*N-N)>>1条边,有人讨论本题是否有向,那是无意义的,因为本题的最小生成树和方向无关。
3 使用Union find是为了判断是否有环,比原始判断快很多。
#include <stdio.h> #include <stdlib.h> const int MAX_VEC = 101; int N; //number of vertices struct SubSet { int p, rank; }; struct Edge { int src, des, wei; }; struct Graph { int V, E; Edge *edge; Graph(int v, int e) : V(v), E(e) { edge = new Edge[E]; } ~Graph() { if (edge) delete[]edge; edge = NULL; } }; static int cmp(const void *a, const void *b) { Edge *a1 = (Edge *) a; Edge *b1 = (Edge *) b; return a1->wei - b1->wei; } SubSet *subs; Edge *res; Graph *gra; void initResource() { subs = new SubSet[N]; for (int i = 0; i < N; i++) { subs[i].p = i; subs[i].rank = 0; } res = new Edge[N-1]; } inline void releaseResource() { if (subs) delete [] subs; if (res) delete [] res; } int find(int node) { if (subs[node].p != node) subs[node].p = find(subs[node].p); return subs[node].p; } inline void unionTwo(int x, int y) { int xroot = find(x); int yroot = find(y); if (subs[xroot].rank < subs[yroot].rank) subs[xroot].p = yroot; else if (subs[xroot].rank > subs[yroot].rank) subs[yroot].p = xroot; else { subs[xroot].rank++; subs[yroot].p = xroot; } } int mst() { initResource(); qsort(gra->edge, gra->E, sizeof(Edge), cmp); for (int i = 0, v = 0; i < gra->E && v < gra->V - 1; i++) { int xroot = find(gra->edge[i].src); int yroot = find(gra->edge[i].des); if (xroot != yroot) { unionTwo(xroot, yroot); res[v++] = gra->edge[i]; } } int ans = 0; for (int i = 0; i < N-1; i++) { ans += res[i].wei; } releaseResource(); return ans; } int main() { int w; while (~scanf("%d", &N)) { gra = new Graph(N, (N*N-N)>>1); int e = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &w); if (j <= i) continue; //下三角形的值不入边 gra->edge[e].src = http://www.mamicode.com/i;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。