POJ2485 Highways(最小生成树)

题意：

城市之间建高速公路，要求在能连通的情况下找出最小生成树最大的边

要点：

最小生成树，这题我学了一下prim算法。这个算法的要点是用点遍历，关键之处在于建立一个不断更新的low数组，这个数组记录生成树的过程中能接触到的对应最小权值。每次先随便选一个顶点作为起点，然后存入low数组，寻找一次当前权值后，集合中顶点的数目增加，能接触到的边改变，所以更新low数组。

Prim算法：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 0xffffff
int 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算法：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
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 <n; ++j){scanf("%d", &temp);if (i != j){e[num].u = i;e[num].v = j;e[num++].len = temp;}}printf("%d\n", kruskal());}return 0;
}