题意：
城市之间建高速公路，要求在能连通的情况下找出最小生成树最大的边
要点：
最小生成树，这题我学了一下prim算法。这个算法的要点是用点遍历，关键之处在于建立一个不断更新的low数组，这个数组记录生成树的过程中能接触到的对应最小权值。每次先随便选一个顶点作为起点，然后存入low数组，寻找一次当前权值后，集合中顶点的数目增加，能接触到的边改变，所以更新low数组。
Prim算法：
| 15341269 | Accepted | 564K | 172MS | 805B | 2016-04-01 19:16:18 |
#include#include #include #define INF 0xffffffint n,maxlen;int map[505][505],low[505];bool vis[505];void prim(){ memset(vis, false, sizeof(vis)); int i,j,mark; for (i = 1; i <= n; i++)//刚开始随便选1作为根 low[i] = map[1][i]; vis[1] = true; for (i = 1; i < n; i++)//注意这里因为1已经放入所以只要遍历n-1次即可 { int min = INF; for (j = 1; j <= n; j++) { if (!vis[j] && min > low[j])//找出最小权值并记录位置 { min = low[j]; mark = j; } } vis[mark] = true; if (maxlen < min) maxlen = min;//题目要求最小生成树中的最长边 for (j = 1; j <= n; j++) if (!vis[j] && map[mark][j] < low[j]) low[j] = map[mark][j];//更新连通后可能接触到的权值 }}int main(){ int t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &map[i][j]); maxlen = 0; prim(); printf("%d\n", maxlen); } return 0;}
Kruskal算法：
| 15341829 | Accepted | 640K | 313MS | 1051B | 2016-04-01 21:14:11 |
#include#include #include #include using namespace std;int num, n;int p[505];struct egde{ int u, v, len;}e[500*500];bool cmp(const egde &a, const egde &b){ return a.len < b.len;}void init(){ for (int i = 0; i < n; ++i) p[i] = i;}int find(int x){ if (x == p[x]) return x; return p[x] = find(p[x]);}bool merge(int x,int y){ x = find(x); y = find(y); if (x != y) { p[x] = y; return true; } return false;}int kruskal(){ init(); int max = -1,edges=0; sort(e, e + num, cmp); for (int i = 0; i < num; ++i) { if (merge(e[i].u, e[i].v)) { if (max < e[i].len) max = e[i].len; edges++; } if (edges + 1 == n) return max; } return -1;}int main(){ int t,temp; scanf("%d", &t); while (t--) { num = 0; scanf("%d", &n); for (int i = 0; i < n; ++i) for (int j = 0; j