poj2421这题我用了Kruskal算法，算法思想:将目前的结点孤立成每个独立的集合，对边进行贪心算法，不断合并小边，化离散为统一，最后统一完所有结点后就是最小生成树了！具体方法:1、将所有的边存入到一个vector中，然后进行升序排序 2、选择当前最短的边，那么相应这条边所连接的两个节点的父亲就统一为编号小的结点的父亲(寻找父亲和合并父亲用到了并查集) 3、用一个m记录当前自由结点的个数(也就是还未并入到最小生成树集合的结点),如果m==n-1那么就证明已经把所有结点都存到了最小生成树种了
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 1e4 + 5; struct edge { int a, b, dist; edge(){}; edge (int x, int y, int z) { a = x, b = y, dist = z; } }; bool cmp(const edge& a, const edge& b) { return a.dist < b.dist; } vector <edge> G; int S[105][105]; int father[maxn]; int n; int findfather(int number) { if (number == father[number]) return number; else father[number] = findfather(father[number]); } int Merge(int a, int b) { //用到了并查集的思想，将不同父亲的结点合并，相同父亲的返回0 int p = findfather(a); int q = findfather(b); if (p == q) return 0; else if (p > q) father[p] = q; //注意是将节点编号大的父节点跟随节点编号小的父节点 else father[q] = p; return 1; } void Init(void) { for (int i = 1; i <= n; i++) { father[i] = i; } } void kruskal(void) { int sum = 0; int len = G.size(); int m = n; //用m记录剩下游走的结点个数 for (int i = 0; i < len; i++) { if (Merge(G[i].a, G[i].b)) { //如果a,b的父节点不同那么它两一定属于不同集合，所以就把两个集合之间的距离加上 sum += G[i].dist; //反之属于同一个集合那么就不必加上距离了，因为没必要合并 m--; if (m == 1) break; //n-1个结点走完，剩下最后一个集合就是最小生成树的结点集合了 } } printf("%d\n",sum); //输出最小生成树的权值 } void addedge(int a, int b, int c) { G.push_back(edge(a,b,c)); } int main(void) { while(~scanf("%d",&n)) { G.clear(); int d; Init(); //初始化节点，使每个节点离散化 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d",&d); S[i][j] = d; } } scanf("%d",&d); //节约变量,用d记录已知铺好的结点数 for (int i = 0; i < d; i++) { int a, b; scanf("%d %d",&a, &b); S[a][b] = 0; //已经铺好了的两点间距离就为零了 } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { addedge(i,j,S[i][j]); } } sort(G.begin(), G.end(), cmp); kruskal(); } return 0; }
