POJ2485 Highways(最小生成树)

题目链接。

分析：

比POJ2253要简单些。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>

using namespace std;

const int maxn = 550;
const int INF = (1<<30);

int G[maxn][maxn], d[maxn], n;

int prim() {
    bool vis[maxn];
    memset(vis, false, sizeof(vis));

    for(int i=0; i<n; i++) {
        d[i] = G[0][i];
    }

    d[0] = 0;
    vis[0] = true;

    for(int i=0; i<n-1; i++) {
        int m = INF, x;
        for(int y=0; y<n; y++) if(!vis[y] && m >= d[y]) m = d[x=y];
        vis[x] = true;
        for(int y=0; y<n; y++)
            if(!vis[y]) {
                int maxx = max(d[x], G[x][y]);
                d[y] = min(d[y], maxx);
            }
    }

    int ans = 0;
    for(int i=0; i<n; i++) {
        ans = max(ans, d[i]);
    }

    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", &G[i][j]);
            }
        }

        printf("%d
", prim());
    }

    return 0;
}

看到有人用其它方法过了，就是prim加了个判断，按着那人思路，再写了一遍。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>

using namespace std;

const int maxn = 550;
const int INF = (1<<30);

int G[maxn][maxn], d[maxn], n;

int prim() {
    bool vis[maxn];
    memset(vis, false, sizeof(vis));

    int maxx = 0;

    for(int i=0; i<n; i++) {
        d[i] = G[0][i];
    }

    d[0] = 0;
    vis[0] = true;

    for(int i=0; i<n-1; i++) {
        int m = INF, x;
        for(int y=0; y<n; y++) if(!vis[y] && m >= d[y]) m = d[x=y];
        vis[x] = true;
        if(maxx < m) maxx = m;
        for(int y=0; y<n; y++) if(!vis[y] && d[y] > G[x][y]) d[y] = G[x][y];
    }

    return maxx;
}

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", &G[i][j]);
            }
        }

        printf("%d
", prim());
    }

    return 0;
}