首页 > 其他 > 详细

学习心得——day2

时间:2015-08-02 23:04:19      阅读:199      评论:0      收藏:0      [点我收藏+]

今天是学习的第二天,主要讲了图论的选题和DP的优化。

图论

图论主要讲了一些扩展的知识。

如:图上删点

给出一个无向图,每个点都有一个权值。
有一些操作,每次操作删除图上所有权值小于一个数的点。
对于每次操作,询问当前和1号点联通的点有多少个。
思路: 对于这个图而言,图上有n个节点,则图最多有n种形态。我们就可以根据权值的大小对节点进行排序,并且按权值的大小将节点依次加入图中,再用并查集维护出在当前状态下与1号节点相连的点的个数。
在这之后针对每一次删除操作,我们找到在它之前的所有操作中取出一个最大值,并直接输出在该权值下的与1号相连的点的个数。
 

ExplorationHDU5222

给出一张既有有向边又有无向边的混合图,问是否存在一条从1到1,且每个点至少经过一次的路径?
思路:针对单纯的无向图,我们可以直接找环;针对单纯的有向图,我们可以找到强连通分量。但是当图中既有有向边又有无向边时,我们往往找不到合适的方法。但是针对
(正在施工中)

学习心得——day2

原文:http://www.cnblogs.com/hy-dgj/p/4694663.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!