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

const int INF = (<<);

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

int prim() {

    bool vis[maxn];

    memset(vis, false, sizeof(vis));

    for(int i=; i<n; i++) {

        d[i] = G[][i];

    }

    d[] = ;

    vis[] = true;

    for(int i=; i<n-; i++) {

        int m = INF, x;

        for(int y=; y<n; y++) if(!vis[y] && m >= d[y]) m = d[x=y];

        vis[x] = true;

        for(int y=; y<n; y++)

            if(!vis[y]) {

                int maxx = max(d[x], G[x][y]);

                d[y] = min(d[y], maxx);

            }

    }

    int ans = ;

    for(int i=; 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=; i<n; i++) {

            for(int j=; j<n; j++) {

                scanf("%d", &G[i][j]);

            }

        }

        printf("%d\n", prim());

    }

    return ;

}

看到有人用其它方法过了，就是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 = ;

const int INF = (<<);

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

int prim() {

    bool vis[maxn];

    memset(vis, false, sizeof(vis));

    int maxx = ;

    for(int i=; i<n; i++) {

        d[i] = G[][i];

    }

    d[] = ;

    vis[] = true;

    for(int i=; i<n-; i++) {

        int m = INF, x;

        for(int y=; y<n; y++) if(!vis[y] && m >= d[y]) m = d[x=y];

        vis[x] = true;

        if(maxx < m) maxx = m;

        for(int y=; 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=; i<n; i++) {

            for(int j=; j<n; j++) {

                scanf("%d", &G[i][j]);

            }

        }

        printf("%d\n", prim());

    }

    return ;

}