查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 
 
 
 

呵呵

2012-9-5 23:49:51 阅读262 评论0 52012/09 Sept5


人要有勇气去改变那些能够改变的事情,有涵养去接受那些不能改变的事情,有智慧去区分哪些是能够改变的、哪些是不能改变的。

作者  | 2012-9-5 23:49:51 | 阅读(262) |评论(0) | 阅读全文>>

二分图匹配

2012-7-23 12:58:37 阅读2830 评论0 232012/07 July23

       前段时间系统的学习了一下二分图匹配,收获还是蛮大的,总算是把最大匹配、点覆盖、点独立、边覆盖什么的关系搞清楚了,基本的算法和定理都会了,剩下的就是建模问题了,这个只能慢慢积累了,最后写个小结。

一、二分图最大匹配
       定义:匹配是图中一些边的集合,且集合中任意两条边都没有公共点,所有的匹配中,边数最多的就是最大匹配。
       算法:用匈牙利算法可以在O(V*E)的复杂度内求出二分图的最大匹配,具体可以看byvoid神犇的blog,讲的很详细,不过想真正完全证明这个算法,得去看组合数学。

二、二分图最小点覆盖
       定义:点覆盖是图中一些点的集合,且对于图中所有的边,至少有一个端点属于点覆盖,点数最小的覆盖就是最小点覆盖。

作者  | 2012-7-23 12:58:37 | 阅读(2830) |评论(0) | 阅读全文>>

[转]天空之城——和你一起,不怕死也不怕活下去

2012-6-29 20:25:49 阅读254 评论0 292012/06 June29


我大概是不觉得辛苦的,哪怕背负着隐晦的秘密面对再凌厉不过的逼迫,哪怕故土此生难回。 
  
只要落下来的时候有你接着我。
不由分说随我穿寒风破冷云寻找一个虚无缥缈的目的地。
毫不迟疑挡住落向我的拳头。
坚定的守护我固执的决定,哪怕知道马上会死掉,也不犹豫的拉住我的手和我一起大声念出咒语。
  
在云和风的顶端,我们摇摇晃晃,你在我身后,你的围巾在我脖子上。

作者  | 2012-6-29 20:25:49 | 阅读(254) |评论(0) | 阅读全文>>

自省

2012-6-29 18:15:37 阅读115 评论1 292012/06 June29

计划性、执行力、不拖沓!什么时候能做到这三点我就牛逼了!!!!!!!!

作者  | 2012-6-29 18:15:37 | 阅读(115) |评论(1) | 阅读全文>>

斯坦纳树

2012-6-26 1:28:16 阅读10448 评论2 262012/06 June26

       最近在看09年姜碧野神牛写的论文《SPFA的优化与应用》,里面提到了一道题——[WC2008]游览计划。这题让我立刻联想到了去年北京赛区的E题,差不多的模型,大概就是在一个图中求给定的k个点的斯坦纳生成树,给定点的个数k<=10。然后昨天做ZOJ月赛的时候一看C题,发现也是几乎一样的模型。可惜当时不会捉,不然就可以升几名了= =!今天折腾了一天,终于想清楚了怎么捉,把三题都AC了,写个简单的小结吧。

       首先我们知道,最优解必然是一棵树,然后这棵树又是由若干棵子树合并成的,于是我们可以状态压缩,把k个节点的连通状态用一个二进制数j表示,dp[i][j]表示以i为根和对应状态为j的节点连通的子树的最小权值。有两种转移方法:

作者  | 2012-6-26 1:28:16 | 阅读(10448) |评论(2) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 

日志分类

 
 
日志分类列表加载中...
 
 
 
 
 

标签

 
 
数据加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

登录  
 加关注