[130308]阶段总结

2019-04-13 12:53发布

站内文章 / 模拟电子
9601 0 1705
开学两周了，一切渐渐重回正轨，电气专业的四大天书之二的模电和电机也渐渐听不懂了…… 放假前的目标只能说是初步达到，对基本的贪心和动态规划有了了解。 最近又杂七杂八的学了些知识，回顾了一些学过的算法，记录如下：
求次小生成树的两种解法 转自：http://blog.sina.com.cn/s/blog_63509b890100r445.html
1：用求最小生成树的方法，求出最小生成树，并记录下该最小生成树上的所有边！
对该生成树上的所有边都进行枚举。对边集中，除了生成树上某条边的集合，构造最小生成树，并记录下最小值！
当生成树上的边枚举完，得到的值的大小就是次小生成树的大小！
2：首先求出原图最小生成树，权值之和为min
枚举添加每条不在最小生成树上的边 ，加上以后一定会形成一个环。
找到环上除了(u,v)以外的权值最大的边，把它删掉，计算当前生成树的权值之和。
枚举完所有边之后，得到的最小值即为次小生成树的权值。
具体实现时，更简单的方法是从每个节点i遍历整个最小生成树
定义F[i][j]为在生成树上，从i到j的路径上最大的边的权值。通过BFS，求出F[i][j]的值
然后对于添加每条不在最小生成树中的边(i,j)，并删去该环中的原生成树的的最大边。
新的生成树权值之和就是Min + w(i,j) – F[i][j]
记录其最小值，则为次小生成树。
 next_permutation STL中的这个全排列库函数十分强大，导致Poj1833直接成了水题……我的代码如下： #include #include using namespace std; int data[1030]; int main () { int T; scanf("%d",&T); while (T--) { int n,k,i; scanf("%d%d",&n,&k); for (i=0;i
最近还做了一场比赛，别人的解题报告在这里：http://www.nbutoj.com/002/

热门文章