zoj 1586 prim

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=586

#include cstdio 

#include cstring 

#define MAX 1000000

int Edge[1010][1010];

int adapter[1010];

int lowcost[1010];

int t,n;

void init( )

 int i, k;

 scanf( "%d", n );

 for( i = 0; i i++ )

 scanf ( "%d", adapter[i] );

 for( i = 0; i i++ )

 for( k = 0; k k++ )

 scanf( "%d", Edge[i][k] );

 if( i == k ) 

 Edge[i][k] = MAX;

 else 

 Edge[i][k] += adapter[i] + adapter[k];

 memset( lowcost, 0, sizeof ( lowcost ) );

void prim( )

 int i, k;

 int sum = 0;

 lowcost[0] = -1;

 for( i = 1; i i ++ )

 lowcost[i] = Edge[0][i];

 for( i = 1; i i++ )

 int min = MAX, j;

 for( k = 0; k k++ )

 if( lowcost[k] != -1 lowcost[k] min )

 j = k;

 min = lowcost[k];

 sum += min;

 lowcost[j] = -1;

 for( k = 0; k k ++ )

 if( Edge[j][k] lowcost[k] )

 lowcost[k] = Edge[j][k];

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

int main( )

 //freopen("1.txt","r",stdin);

 scanf ( "%d", t );

 for ( int i = 0; i i ++ )

 init( );

 prim( );

 return 0;

Prim 复习acwing算法基础课的内容，本篇为讲解基础算法：Prim，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
[HDU 4738] Caocao‘s Bridges | Tarjan 求割边 Problem Description Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn’t give up. Caocao’s army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river,
John von Neumann, b. Dec. 28, 1903, d. Feb. 8, 1957, was a Hungarian-American mathematician who made important contributions t...