首页 > 代码库 > 140704
140704
今天收获还算可以把。。
今天过了poj1258和poj1753.
1258是一个红果果的最小生成树,写了个prim,用的邻接矩阵。
当然邻接表不是很会用,回头会研究图算法,短期内会看的。
关于prim算法,比较重要的就以下几个点。
1.选取一个点,然后据此更新其他节点的low[]信息
2.再执行n-1次操作,每次操作选取木有标记的点中low最小的那个。记得每次增加节点就要更新low数组
low[i]表示,从i节点到已经生成区域的最短路径。。
然后,其他的没什么,注意用个vis数组记录标记状态。
代码如下:poj1258
[cpp] view plaincopy
- #include <stdio.h>
- #define N 300
- #define INF 300000
- int a[N][N];
- int ans;
- int vis[N];
- int low[N];
- int prim(int n)
- {
- int i,j;
- int pos;
- /*
- * 更新low数组很重要,之前写了一个,没有更新low
- * */
- for(i=0;i<n;i++)
- {
- vis[i]=0;
- }
- vis[0] = 1;
- pos = 0;
- int min;
- int result=0; /*我屮艸芔茻,没初始化成0,,查错查了半天*/
- for(i=1;i<n;i++)
- {
- low[i] = a[pos][i];
- }
- for(j=1;j<n;j++)
- {
- min = INF;
- for(i=0;i<n;i++)
- {
- if(vis[i]==0 && min>low[i])
- {
- min = low[i];
- pos = i;
- }
- }
- vis[pos]=1;/*标记这个新加入的点已经走过*/
- result+=min;
- /* printf("min:%d,%d\n",min,result);*/
- /*
- * 这是选出了新的节点,下面要更新和这个节点关联的low数组
- * */
- for(i=0;i<n;i++)
- {
- if(vis[i]==0 && a[pos][i]<low[i])/*刚开始第一个条件写成了i!=pos,这样会导致之前节点呗更新*/
- low[i] = a[pos][i];
- }
- }
- return result;
- }
- int main()
- {
- int n;
- int i,j;
- while(scanf("%d",&n)!=EOF)
- {
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- {
- scanf("%d",&a[i][j]);
- }
- ans = prim(n);
- printf("%d\n",ans);
- }
- return 0;
- }
解题报告没什么可说的了,解析prim的帖子一抓一把。
然后是做了poj1753,这题是用一个BFS做的。自己写一个循环队列。
集训结束了我会写个报告的,暂时留空做个标记在这里~~
传送门:poj1753。
然还是,听学长讲了个单调栈。
poj2559,单调栈(这题今天估计来不及看了!!学长讲的挺好的)
明后天要做掉。当然尽量把,反正这个思路特别厉害。嗯。好东西。希望有时间去做~
然后今天鱼头讲了查找和排序。
关于归并排序,快速排序,堆排序,最近几天要研究研究,,快速排序的话,这个帖子不错:
http://blog.csdn.net/morewindows/article/details/6684558
分了小组,,我是个四人小组的组长。。加油加油
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。