今天brent講座，我竟然忘了！！！郁悶的要死，幸好是去上自習了，不然會更后悔。。。今天他講的生成樹，這個我還會一點，多多少少能自我安慰一下，不過在看課件的時候還是有所收獲，發(fā)現(xiàn)在實現(xiàn)最小生成樹的時候可以有兩種方法，差別特別小，但時間還是差一點的，不幸的是我原來的方法正是那個稍微慢一點的。簡單來說，有三個差別：
1):在初始化dis數(shù)組時一個初始化為map[s][i]，(包括dis[s],其中s為源點)，另一個初始化為無窮大，dis[s]=0；
2):一個將將flag[s]標記為true，另一個標記為false
3):最重要的一點，一個循環(huán)n-1次，一個循環(huán)n次
我把兩個算法貼出來對比一下：
16ms的：
1
#include<stdio.h>
2#include<string.h>
3#include<stdlib.h>
4#define INF 0x1f1f1f1f
5#define M 102
6int map[M][M],dis[M];
7bool flag[M];
8
int prim(int s,int n)
{
9
int i,j,md,temp,total=0;
10 memset(flag,false,sizeof(flag));
11 flag[s]=true;
12 for(i=1;i<=n;i++)
13 dis[i]=map[s][i];
14
for(i=1;i<n;i++){
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 temp=j;
19 md=dis[j];
20
}
21 }
22 total+=md;
23 flag[temp]=true;
24 for(j=1;j<=n;j++)
25 if(!flag[j]&&map[temp][j]<dis[j])
26 dis[j]=map[temp][j];
27 }
28 return total;
29
}
30int main()
31{
32 int i,j,k,n,cas;
33 while(scanf("%d",&n)!=EOF){
34 for(i=1;i<=n;i++)
35 for(j=1;j<=n;j++){
36 scanf("%d",&map[i][j]);
37 if(map[i][j]==0) map[i][j]=INF;
38 }
39 printf("%d\n",prim(1,n));
40 //system("PAUSE");
41 }
42}
0ms的：
1#include<stdio.h>
2#include<string.h>
3#include<stdlib.h>
4#define INF 0x1f1f1f1f
5#define M 102
6int map[M][M],dis[M];
7bool flag[M];
8int prim(int s,int n){
9 int i,j,md,temp,total=0;
10 memset(flag,false,sizeof(flag));
11 memset(dis,0x1f,sizeof(dis));
12 dis[s]=0;
13 for(i=1;i<=n;i++){
14 md=INF;
15 for(j=1;j<=n;j++){
16 if(!flag[j]&&dis[j]<md){
17 temp=j;
18 md=dis[j];
19 }
20 }
21 total+=md;
22 flag[temp]=true;
23 for(j=1;j<=n;j++)
24 if(!flag[j]&&map[temp][j]<dis[j])
25 dis[j]=map[temp][j];
26 }
27 return total;
28}
29int main()
30{
31 int i,j,k,n,cas;
32 while(scanf("%d",&n)!=EOF){
33 for(i=1;i<=n;i++)
34 for(j=1;j<=n;j++)
35 scanf("%d",&map[i][j]);
36 printf("%d\n",prim(1,n));
37 }
38}
39
以后要學會用這個快的。。。~