Victordu

算法

普里姆:O(n*2) ,與圖中邊數無關，該算法適合于稠密圖.
1）設最小生成樹T的V（T）和E（T）均為空。
（2）從頂點集V（G）中任取一頂點加到頂點集V（T）中。??????????????????????
（3）在與V（T）中各頂點相關聯的所有邊中，取一條權值最小的邊（Vi，Vj）其中，Vi包含于V（T），Vj含于 V（T)。???????????????????????????????????
(4）將邊（Vi，Vj）加入到E（T）中，將頂點Vj到入到V（T）中.（5）若V（T）已滿n個頂點，則算法終止，否則轉步驟（3）。都是很典型很容易AC的
在這里挑一個最典型的題目貼上代碼

/**********************
Author: WHU_Victordu
Created Time: 2008-1-2
File Name: pku1258.cpp
? Description:?
???**************************/

#include <stdio.h>
#define MAXNUM 100000

int dis[101][101],low[101];

int main()
{
??? int n,i,j,min,k,sum;
?
??? while(scanf("%d",&n)!=EOF)
??? {
???????? sum=0;?????
?????? for(i=0;i<n;i++)
???????? for(j=0;j<n;j++)
???????? scanf("%d",&dis[i][j]);
??????
?????? for(i=0;i<n;i++)
?????? low[i]=dis[0][i];
???
????? low[0]=0;
?????
????? for(i=1;i<n;i++)
????? {
??????? min=MAXNUM;
??????? j=k=1;
???????
??????? while(j<n)
??????? {
????????? if(low[j]&&low[j]<min)
????????? {
??????????? min=low[j];
??????????? k=j;
????????? }
????????? j++;
??????? }
???????
??????? sum+=low[k];
???????
??????? low[k]=0;
???????
??????? for(j=1;j<n;j++)
??????? {
????????? if(dis[k][j]<low[j])
????????? low[j]=dis[k][j];
??????? }
????????
????? }
?????
????? printf("%d\n",sum);
?????
??? }
}