二分图匹配总结

对于任意图:

|最小边覆盖|+|最大匹配|=|V|

二分图的最大匹配=最小点覆盖数

对于二分图:

以下数值等价.

最大匹配

最小点覆盖

|V|-最大独立集(二分图or有向无环图)

|V|-最小边覆盖数

|V|-最小路径覆盖数(有向无环图)

|V|-最小路径覆盖数/2(无向图)

(上面括号里有有向无环图的,均是将一个点拆成两个点连边匹配)

由于任意图的那几个几乎用不到于是这里只贴二分图的定义

最小点覆盖:理解为点覆盖边,即用最小的点覆盖所有的边。(若一条边的其中一个端点被选用,这条边就被覆盖了)

最大独立集:求一个最大的点集,里面的点不存在任何的边相连。

最小边覆盖:理解为边覆盖点,用最少的边把图中的点全部覆盖。

最小路径覆盖:用最少的路径把图中的所有点覆盖。

另外:最大独立集与最小覆盖集互补。

推广到有权的形式也一样,即最大点权独立集最小点权覆盖集互补

求最小点权覆盖集可以这样求:

先对图黑白染色,然后向白色的点放X部,黑色的点放Y部。

1、连边[S,i],容量等于i的点权。(对于二分图的X集)

2、连边[i,T],容量等于i的点权。(对于二分图的Y集)

3、对于有边的i和j连边[i,j](i∈X,j∈Y),容量为INF

最后得出的最大流就是最小点权覆盖,实际上是最小割与之对应。

对于求了传递闭包以后的有向无环图:

最大反链=|V|-最大匹配

SEARCH总结

这段时间做了不少seach。现在来总结一下。

1、关于dfs和dfs-id。

应当考虑到的剪枝有:上界,下界,可行性剪枝,最优性剪枝。

TIPS:也许给数据排下序会有更强大的剪枝。

2、bfs

hash很重要

3、双向bfs

动态调整搜索方向很重要,即取节点少的一边去扩展。

4、A*

这个是老大,这个是重点,传说中最快的搜索。

f(s)=g(s)+h(s)——h是估价函数。

再次来重点:

估价函数h(s)的条件:1、h(s)必须是从s到达目标点的下界。2、h(s1)<=h(s2)+c[s1,s2]。c是转移代价。

然后是A*的实现:

一个堆,一个hash list(没有删除操作)。然后每次取堆顶元素(注意,堆顶元素的f值不可能再次改变)

然后扩展,如果扩展出来的节点hash list里没有,那就加入堆,否则如果扩展出来的点的F值小于堆中的,就更新堆。然后当目标节点出现在堆顶的时候,就可以输出了。因为堆顶元素的f值不可能再次改变了。

后缀数组学习笔记

首先定义:

rank[i]为S[i..n]这个后缀是所有后缀里第几大的。

sa[i]为第i大的后缀是哪一个

因为后缀不可能相等,所以rank[i]和sa[i]唯一,且满足sa[rank[i]]=i

我们可以通过类似多关键字排序+构造Sparse Table的方法使构造这两个数组的时间复杂度为O(nlgn)

注意中间过程用基数排序,否则用qsort的话会变成O(n(lgn)^2)

构造完这个,我们还应该加一个height数组,height[i]表示lcp(i-1,i)。

其中i表示排名,即rank[sa[i]]=i

这样就相当于后缀树中两个相邻节点的lca了。

至于如何构造height[i],这里有我写的code。

其中使用了一个定理:

height[i]>=height[sa[i]-1]-1(看懂什么意思以后,证明显然)

使用这个定理以后构造height的复杂度降到了O(n)

void lcp(){
     memset(height,0,sizeof(height));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st,j,k;
         st=max(height[rank[i-1]]-1,0);
         j=i+st;
         k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]){
               st++;
               j++;
               k++;
         }
         height[rank[i]]=st;
     }
}

另外再有一个定理lcp(i,j)=min(lcp(k-1,k)) (k∈(i,j])

姑且叫他lcp(i,j)定理

然后我们就可以用它解决很多问题。

总的来说有:

1、多串匹配。

复杂度O( (T+lgN)*M)   其中T为模式串长度,N为主串长度,M为模式串个数。

主要思想就是二分,然后利用height数组,和lcp(i,j)定理。

2、最长公共前缀。

例题:http://hi.baidu.com/edwardmj/blog/item/a69c46560990d5143a2935fb.html

就是max(height[i])

3、最长回文子串。

设给定S',求其最长回文子串。(设其长度为n)

令S''为S'的倒序串(即S''[n-i+1]=S'[i])

然后S=S'+'#'+S''。(即把两串连接)(长度为2*n+1)

然后枚举中心i(1<=i<=n),其镜像中心为2*n+2-i

然后就是求最多能延伸多长。

即求lcp(i,i')。利用lcp(i,j)定理加上Sparse Table(RMQ)就可以做到在O(1)的复杂度内解决延伸问题。

所以,求最长回文子串的部分,复杂度为O(N)

总复杂度O(nlgn)(加上构造时间)

4、利用分组思想做一些意想不到的操作.

例如:http://hi.baidu.com/edwardmj/blog/item/e5105b8d97842ef1513d92ed.html

C++随机学习笔记

一直还在用pascal做数据。。。现在终于学会了C++的随机。

首先需要

#include

写一个srand((unsigned)time(NULL)) (随机种子)

然后就可以这样用了。t=rand()%xxxx;

但是比赛的时候是不允许读时间的,所以比赛的时候直接rand()就可以得到一串随机数。但是每次运行程序的结果是一样的(但每次rand()的结果不一样)。

所以做数据对拍的时候我们可以用那个随机种子。

比赛时直接rand()就可以了。