http://poj.org/problem?id=2485

　　這是道最小生成樹的題目，求的是最小生成樹中最大邊的權值。開始就想到用kruskal算法去做，

因為邊是從小到大排序的，所以保證最后一條加入生成樹的邊的權值是最小生成樹當中最大的。

Kruskal僅排序用的時間是O（mlog m）,其中m 為n^2數量級的，為邊的總數。

?????? 再說說prim算法，這個算法嚴格來說是今天才學的。在我看來，prim算法的精髓在于傳遞，建

立最小生成樹的方法就是一個傳遞的過程，先將編號為0的點作為樹根，然后找到離0最近的一點j，加

入生成樹中，然后找離j最近的，每次都要更新lowc的值。找最大邊的權值話就每次用加入的minc值

與max比較就行了。

下面是兩種不同算法的代碼：

/*
kruskal算法
Memory: 812K Time: 329MS
Language: C++ Result: Accepted
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int MAXN = 505;
int u[MAXN * MAXN], v[MAXN * MAXN], w[MAXN * MAXN], p[MAXN], r[MAXN * MAXN];
int e1, res, n, m;

int find_set( int x)
{
return p[x] == x ? x : ( p[x] = find_set( p[x]));
}

int cmp( const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return w[*p] - w[*q];
}

void kruskal()
{
//res = 0;
for( int i = 0; i < n; i ++) p[i] = i;
for( int i = 0; i < m; i ++) r[i] = i;
qsort( r, m, sizeof(r[0]), cmp);
for( int i = 0; i < m; i ++)
{
int e = r[i]; int x = find_set(u[e]), y = find_set(v[e]);
if( x != y) { res += w[e]; p[x] = y; e1 = e;}
}
}

int main()
{
int T;
scanf( "%d", &T);
while( T --)
{
scanf( "%d", &n);
m = 0;
for( int i = 0; i < n; i ++)
for( int j = 0; j < n; j ++)
{
u[m] = i, v[m] = j;
scanf( "%d", &w[m ++]);
}
kruskal();
printf( "%d\n", w[e1]);
}
return 0;
} /*
prim算法
Memory: 564K Time: 141MS
Language: C++ Result: Accepted
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int MAXN = 505;
bool vis[MAXN];
int w[MAXN][MAXN], lowc[MAXN], max, n, res;
const int INF = 0x3F3F3F3F;
void prim()
{
max = 0;
//res = 0;
int minc, p;
memset( vis, false, sizeof vis);
vis[0] = true;
for( int i = 1; i < n; i ++) lowc[i] = w[0][i];
for( int i = 1; i < n; i ++) {
minc = INF, p = -1;
for( int j = 0; j < n; j ++)
if( !vis[j] && minc > lowc[j]){
minc = lowc[j];
p = j;
}
vis[p] = true;
max = max > minc ? max : minc;
//res += minc;
// 更新lowc[j]的值。
for( int j = 0; j < n; j ++)
if( !vis[j] && lowc[j] > w[p][j])
lowc[j] = w[p][j];
}
}

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", &w[i][j]);
prim();
printf( "%d\n", max);
}
return 0;
}

今天想著將kruskal算法的寫法改了下，記錄樹中邊的數目，有n-1條邊后跳出循環，省了那么一點時間。

/*Accepted 800K 282MS C++ 1373B 2012-07-24 08:40:52*/ #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std;const int MAXN = 505; int p[MAXN], r[MAXN * MAXN], u[MAXN * MAXN], v[MAXN * MAXN], w[MAXN * MAXN]; int n, m, ret;bool cmp( const int i, const int j) {return w[i] < w[j]; }int find(int x) {return p[x] == x ? x : (p[x] = find(p[x])); }void init() {int i, j, val;m = 0;for( i = 1; i <= n; i ++)for( j = 1; j <= n; j ++){scanf( "%d", &val);if(i == j) continue;u[m] = i, v[m] = j, w[m ++] = val;} }void kruskal() {int ans, cnt, e;ans = cnt = 0;int nx, ny, i, j;for( i = 1; i <= n; i ++)p[i] = i;for( i = 0; i < m; i ++)r[i] = i;sort( r, r + m, cmp);for( i = 0; i < m; i ++){e = r[i];nx = find(u[e]), ny = find(v[e]);if( nx != ny){p[nx] = ny;ans += w[e];cnt ++;if( n - 1 == cnt) {ret = w[e];break;}}} }int main() {int T;scanf( "%d", &T);while( T --){scanf( "%d", &n);init();kruskal();printf( "%d\n", ret);//printf( "\n"); }return 0; }

?

?

轉載于:https://www.cnblogs.com/Yu2012/archive/2012/03/31/2427775.html

總結

以上是生活随笔為你收集整理的POJ 2485-Highways的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。