今天brent讲座，我竟然忘了！！！郁闷的要死，幸好是去上自习了，不然会更后悔。。。今天他讲的生成树，这个我还会一点，多多少少能自我安慰一下，不过在看课件的时候还是有所收获，发现在实现最小生成树的时候可以有两种方法，差别特别小，但时间还是差一点的，不幸的是我原来的方法正是那个稍微慢一点的。简单来说，有三个差别：
1):在初始化dis数组时一个初始化为map[s][i]，(包括dis[s],其中s为源点)，另一个初始化为无穷大，dis[s]=0；
2):一个将将flag[s]标记为true，另一个标记为false
3):最重要的一点，一个循环n-1次，一个循环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
以后要学会用这个快的。。。~