對酒當歌,人生幾何? 譬如朝露,去日苦多

admin 发布的文章

第一步
开始学习二分图需掌握。
1.增广路径是什么?
其实二分图就是找增广路径,每找到一条增广路径,ans++。所以要弄清增广路径是什么。
2.掌握匈牙利算法。
匈牙利算法就是找增广路径的,所以掌握后就算真正学会二分图。


困惑:
1.无向二分图?有向二分图?
无向二分图:
比如u跟v是增广路,由于每个点都跑了一次,那么u-v和v-u都找了一次,那么无向二分图最后找的是最大匹配点。
有向二分图:
如果有这样三个点,a到b,b到c。那么找的时候肯定会找两次,最后是match[b]=a,match[c]=b。所以相当于找了一条路(a->b->c)上边数。


第二步
二分图最小路径覆盖
目的:找出最少路径数覆盖所有点。(什么样的路径由题目定义)
无向图:单纯的找出最少路径数覆盖所有点的话。
结论:ans=n-二分图最大匹配/2。
想一下无向图最大二分图匹配找出了最多匹配了多少点,那覆盖这些点只需(二分图最大匹配/2)个点,其他点都需要一条边,所以是其他点需要(n-二分图最大匹配)个点,相加得出结果。

有向图:如果一个士兵在u点,他能顺路一直走下去,但不能回走,问需要多少个这样的士兵。
结论:ans=n-二分图最大匹配。
前面已经说过了,有向二分图相当与找到一条路径上的边数,那么找到问题所问的点就很简单了,n-二分图最大匹配。
第三步
二分图最小点覆盖数
目的:选取最少的点,使任意一条边至少有一个端点被选择,图应该形成一个树。
结论:ans=二分图最大匹配。
二分图最大匹配完以后肯定都是由增广路径得来的,那么由增广路径的定义我们可以想到。
~9)@H$}NBL$YM(@$`S32~~J.png

看上一次的博客好像是3.5号,好久没更新了,好像一直在准备省赛,一直在做题,感觉自己其实还是偷懒的时候多,比如现在,本来应该刷题,但是却在感慨最近发生的事。
过年的时候有两个愿望,但是一个却都没有实现,现在也是倍感无聊,想不到星期天做什么比较好,打王者(玩够了,不想在玩了),吃鸡(头晕,难受,还是想好好休息一下),出去看个电影(没有人陪,实在是尴尬)。。。所以我周日就没事干了。应该就是洗洗衣服,看看娱乐节目,然后领个快递就结束明天的日程了吧!
最近在回味《龙族》,看1的时候,刚开始看得实在是孤独,最后被诺诺接走,应该算是他人生的救世主吧!看第三部,奔这绘梨衣去的,也需是回味自己对XX的向往吧,但是我已不是那个小孩子了,那样的人世界上是不会有的,每个人都有自己的苦衷,而且不会那么单纯,但是看完路明非和绘梨衣相处的6天后,我还是沉默了,深深陷入对绘梨衣的向往,与对路明非的羡慕与不甘吧!(那明天就看龙族2吧!)
最近的生活就是这样,已经不像上个学期那样喜欢搞博客了,而且内容质量不是很高,也需以后就会消失吧!

看这部番的缘由是因为听了Lex的推荐吧,听说是刀剑神域同期作品,却没有打过刀剑神域。
看完之后真是为《冰菓》惋惜啊!
喜欢这部番的缘由,是没有的,就像喜欢一个人一样,不需要什么理由,就是有感觉,内心不能平静。
硬要说的话。
这部番是2012年制作的,但是放在现在来看,画面的质量依然胜过大多数动漫。
我也从这个动漫体会到了青春的气息。
男主折木的性格真的有意思。
女主超级萌!
实在是无法用语言来形容啦!就是内心激动久久不能平静!
644960.png704736.jpg

优质博客推荐

问题描述:母串S,子串T,求S[i]~S[n-1] (0<=i<n) ,与T的最长公共前缀extend[i]。

求解需要next数组辅助,next[i]表示next[i]~next[m-1]与next[0]~next[m-1]的最长公共前缀。

我们直接讨论在中间时匹配的情况。

已知:

1.假如我们extend已经求到了k,该求k+1了。

2.位置p代表extend[0,k]能匹配到的最远的位置,并且设取这个最大值的位置为po。

3.next数组已知,next[k+1]=len。

求extend数组

一。k+len<p

如上图

此时extend[k+1]=next[k+1]=len;

S[k+len+1]不会等于T[len],如果它们相等,那么就表示T[k+len-1-po]==T[len],那么next[k+1]=len+1,冲突,那么错误。

二。k+len>=p

因为我们最远才匹配到p,所以S[p+1]以后的字符和T[p-k]以后的字符一一开始匹配,直到失配为止。

如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。

然后求extend就结束了,而求next数组就和extend一样了,只不过把母串换了换。