首页 > 代码库 > 140704

140704

今天收获还算可以把。。

 

今天过了poj1258和poj1753.

1258是一个红果果的最小生成树,写了个prim,用的邻接矩阵。

当然邻接表不是很会用,回头会研究图算法,短期内会看的。

关于prim算法,比较重要的就以下几个点。

 

1.选取一个点,然后据此更新其他节点的low[]信息

2.再执行n-1次操作,每次操作选取木有标记的点中low最小的那个。记得每次增加节点就要更新low数组

low[i]表示,从i节点到已经生成区域的最短路径。。

 

然后,其他的没什么,注意用个vis数组记录标记状态。

代码如下:poj1258

 

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
 
  1. #include <stdio.h>  
  2. #define N 300  
  3. #define INF 300000  
  4. int a[N][N];  
  5. int ans;  
  6. int vis[N];  
  7. int low[N];  
  8. int prim(int n)  
  9. {  
  10.     int i,j;  
  11.     int pos;  
  12.     /* 
  13.      * 更新low数组很重要,之前写了一个,没有更新low 
  14.      * */  
  15.     for(i=0;i<n;i++)  
  16.     {  
  17.         vis[i]=0;  
  18.     }  
  19.     vis[0] = 1;  
  20.     pos = 0;  
  21.   
  22.     int min;  
  23.     int result=0;  /*我屮艸芔茻,没初始化成0,,查错查了半天*/  
  24.     for(i=1;i<n;i++)  
  25.     {  
  26.         low[i] = a[pos][i];  
  27.     }  
  28.     for(j=1;j<n;j++)  
  29.     {  
  30.         min = INF;  
  31.         for(i=0;i<n;i++)  
  32.         {  
  33.             if(vis[i]==0 && min>low[i])  
  34.             {  
  35.                 min = low[i];  
  36.                 pos = i;  
  37.             }  
  38.         }  
  39.         vis[pos]=1;/*标记这个新加入的点已经走过*/  
  40.           
  41.         result+=min;  
  42.     /*  printf("min:%d,%d\n",min,result);*/  
  43.         /* 
  44.          * 这是选出了新的节点,下面要更新和这个节点关联的low数组 
  45.          * */  
  46.         for(i=0;i<n;i++)  
  47.         {  
  48.             if(vis[i]==0 && a[pos][i]<low[i])/*刚开始第一个条件写成了i!=pos,这样会导致之前节点呗更新*/  
  49.                 low[i] = a[pos][i];  
  50.         }  
  51.   
  52.     }  
  53.   
  54.   
  55.     return result;  
  56.   
  57. }  
  58. int main()  
  59. {  
  60.     int n;  
  61.     int i,j;  
  62.     while(scanf("%d",&n)!=EOF)  
  63.     {  
  64.         for(i=0;i<n;i++)  
  65.             for(j=0;j<n;j++)  
  66.             {  
  67.                 scanf("%d",&a[i][j]);  
  68.             }  
  69.         ans = prim(n);  
  70.         printf("%d\n",ans);  
  71.   
  72.     }  
  73.     return 0;  
  74. }  


解题报告没什么可说的了,解析prim的帖子一抓一把。

 

 

然后是做了poj1753,这题是用一个BFS做的。自己写一个循环队列。

集训结束了我会写个报告的,暂时留空做个标记在这里~~

 

传送门:poj1753。

 

然还是,听学长讲了个单调栈。

poj2559,单调栈(这题今天估计来不及看了!!学长讲的挺好的)

明后天要做掉。当然尽量把,反正这个思路特别厉害。嗯。好东西。希望有时间去做~

 

然后今天鱼头讲了查找和排序。

关于归并排序,快速排序,堆排序,最近几天要研究研究,,快速排序的话,这个帖子不错:

http://blog.csdn.net/morewindows/article/details/6684558

 

 

分了小组,,我是个四人小组的组长。。加油加油