POJ2485 Highways(最小生成树)

时间:2023-01-05 08:24:23

题目链接

分析:

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