POJ 2485 – Highways [Kruskal或Prim]

vjudge链接

题意:有n个村庄,给定任意两个村庄之间的距离,要求建立一些公路能够连接起所有村庄,求出这些公路中的最长的公路的长度。

分析:求最小生成树中的最大边权,可以用Kruskal也可以用Prim算法。

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;
}

欢迎留言