差不多就要CCF考试了，弱鸡我还是挺慌的（好想上400分保研~），最近开始来逐渐巩固自己所储备的知识。
CCF的第四题往往是图论，今天就来回顾一下经典的最小生成树算法：Kruskal && Prim。
边用结构体数组存储，属性有：两个端点，权值。
将所有边由小到大排序， 以最短的边为算法的起始。依次遍历剩下的边，结合并查集判断是否会形成强连通，不行成强连通的剩下边加入到树中。截止条件，边数 == 点数 - 1。
个人容易出错的地方：
1）并查集的Unite函数中，两个点的根节点应要通过FindRoot函数来查找，而不是直接用Root【】数组（数组存储的是父节点，单并不一定是祖宗节点），连通性是通过最祖宗的节点是否相连来判断的。
2）遇到多组测试用例时，要记得将重复使用的量重新初始化。
代码（待）：明天就写哈~
由于边较密集，用邻接矩阵table【】【】来存边，存边权时注意边的双向性。
用minCnt【】数组存所有点到树的距离，个人习惯以1为初始的树根st（哪个点都无所谓，因为所有点都要取到），即初始的minCnt为所有点到st点的距离table[st][index]。
vis【】标记点进入树的情况。
先初始化minCnt，标记我们的st点（初始的树），因为已经找到一个点了，所以之后是一个总点数 - 1次的循环，即 n - 1 次， 找到剩下的 n - 1个点。在这个大循环中，每次遍历剩下的点，找到到树距离最短的（用minLen存最短距离，minNode存最小的点的编号，桶排思想），标记入树，同时累加树的总权值。接着，由于树的扩张，我们需要更新剩下点到树的最小距离minCnt， 又是一个循环。总体上就是，一个大循环，内嵌两个小循环。
个人容易出错的地方：
1）这里各点到树的距离会随着树的生成不断变化，所以没有必要一开始sort排序，每次查找时用循环桶排就好。
2）最初始的点就是初始的树，所以到树的距离为0，minCnt【st】 = 0。
这里贴一道CCF的第四题（这是比较早的CCF题，所以不难，竟然只是个模板题~），顺便扇自己一巴掌--我做题时，一看以为是求单源最短路径，上来就敲spfa，结果浪费了时间。真正考试时要稳一点，在纸上大致模拟一遍思路看是否符合题意再开始写。
//minimum spanning tree //边较多，用prim #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define Inf 0x3f3f3f3f #define ll long long const int maxp = 1000 + 2, st = 1; int table[maxp][maxp], minCnt[maxp]; // 到树的距离 bool vis[maxp]; int n, m, a, b, c, cntp; ll sumw; void Prim() { for(int i=2;i<=n;++i){ minCnt[i] = table[st][i]; } minCnt[st] = 0; vis[st] = true; //第一个节点入树 for(int t=1; t < n; ++t){//找到剩下的n-1个节点 int minNode = 0, minLen = Inf; for(int j = 1; j <= n; ++j){ if(!vis[j] && minCnt[j] < minLen){ minLen = minCnt[j]; minNode = j; } else continue; } sumw += minLen; //生成的一支的权值 vis[minNode] = true; for(int j = 1; j<= n; ++j){ if(!vis[j]){//更新到树的距离 minCnt[j] = min(minCnt[j], table[minNode][j]); } } } } inline int read(){ char ch = getchar(); int ans = 0; while(ch < ‘0‘ || ch > ‘9‘) ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘){ ans = (ans << 3) + (ans << 1) + ch - ‘0‘; ch = getchar(); }return ans; } int main() { n = read(), m = read(); memset(table, Inf, sizeof(table)); while(m--){ a = read(), b = read(), c = read(); table[a][b] = table[b][a] = min(table[a][b], c); } Prim(); printf("%lld\n", sumw); return 0; }
原文：https://www.cnblogs.com/GorgeousBankarian/p/11144382.html