#### POJ 2485 – Highways [Kruskal或Prim]

vjudge链接

Kruskal：

```#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 200000;
int pa[maxn];

struct Edge{
int from, to, cost;
bool operator < (const Edge & rhs) const {
return cost < rhs.cost;
}
}v[maxn];

void Init(int n) { for(int i = 0; i <= n; ++i) pa[i] = i; }
int Find(int x) { return pa[x]==x ? x : pa[x] = Find(pa[x]); }

int main() {
int T; scanf("%d", &T);
while(T--) {
int n, m = 0; scanf("%d", &n); Init(n);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
int d; scanf("%d", &d);
if(j > i) {
v[m].from = i; v[m].to = j;
v[m++].cost = d;
}
}
}
sort(v, v + m);
int cnt = 0, best = -0x7f7f7f7f;
for(int i = 0; i < m; ++i) {
int rx = Find(v[i].from), ry = Find(v[i].to);
if(rx != ry) {
pa[rx] = ry;
best = v[i].cost;
if(++cnt >= n - 1) break;
}
}
printf("%d\n", best);
}
return 0;
}
```

Prim：

```#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int inf = 0x7f7f7f7f, maxn = 512;
bool vis[maxn];
int n, lowc[maxn], cost[maxn][maxn], best;

int Prim() {
int ans = 0;
memset(vis, 0, sizeof(vis)); vis[0] = true;
for(int i = 0; i < n; ++i) lowc[i] = cost[0][i];
for(int i = 1; i < n; ++i) {
int minc = inf, p = -1;
for(int j = 0; j < n; ++j)
if(!vis[j] && lowc[j] < minc) {
minc = lowc[j];
p = j;
}
if(minc >= inf) return -1;
ans += minc;
best = max(best, minc);
vis[p] = true;
for(int j = 0; j < n; ++j) {
if(!vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
}
}
return ans;
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", &cost[i][j]);
best = -inf; Prim();
printf("%d\n", best);
}
return 0;
}
```