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

分类 ACM算法 下的文章

1.以前学的KMP比较急,其实根本不懂。(重学了一遍,彻底理解)

2.暴力匹配就不多说了,那么有什么办法可以优化呢?那就是向前移动多个位置,但是在移动多个位置的同时,必需满足的是要匹配的字符串必需在前面出现过,而且是从开头,不然你无法判断在移动之后,开头那部分是否相同,这一点应该好想。(其实就是找每个所有字串的前后缀是否相等)

3.next数组保存的就是,如果不匹配就从j=next[j]开始向后匹配(其实就是跳到next[j]这个位置,重新比较)

4.那么怎么构造next数组呢?找i和j记录主串和模式串各自的位置,如果匹配就继续同时向后移,如果不相等,主串的i就需要移回起点,继续寻找前后缀相等的字符串。

网络流之最大流

1.EK算法

跑一遍bfs找到这条路上的最小边minn,sum+=minn,回溯,正向边-minn,反向边+minn。重复这个过程直到没有路可跑。

2.FF算法

跑dfs找到终点,确定最小边minn,回溯,正向边-minn,反向边+minn,sum+=minn,重复整个过程直到没有路可跑。

3.Dinic算法

bfs建立图层,dfs深搜。

1.学习链接:http://blog.csdn.net/mystery_guest/article/details/51910913

kuangbin专题分类

一. 二分匹配

先看一下理论理解一下:http://www.renfei.org/blog/bipartite-matching.html

然后趣学匈牙利算法:一遍就看懂

A,B,C,D,E,G

1.交叉染色判断二分图。

2.二分图最小点覆盖(König定理证明)(好像只能无向,对吧?)

I,

感谢Matrix   

感谢:http://blog.csdn.net/kootain/article/details/6692582?utm_source=jiancool

其实就是二分图最大匹配,要换个角度思考。

二分图最大匹配匹配到的点为集合M。x点属于左集合,y点属于右集合,且x点和y点不属于M,那么x,y点一定没有路相连,因为它们不属于集合M。所以除集合M的点外,其他点与之相连的边一定属于M,M中的点是二分图最大匹配,所以就相等,但是有向要改为无向进行二分图最大匹配。

3.

无向图二分图最小路径覆盖,

H,

无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2

一开始我想时是这样的样例,有7个点,经过匹配1和5,2和4,3和6,7单出来。所以我以为是(二分图最大匹配+1)/2,但是发现我只考虑了一个图,如果他有好几个图,我就完了,所以上面的公式补全了我的思想。

有向图二分图最小路径覆盖和求最大独立子集

有向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数

感谢:http://blog.sina.com.cn/s/blog_89a06c7d0100trcg.html

也就是 最大独立子集=顶点个数-最小顶点覆盖(最大二分匹配数)

先假设一个二分图模型,A集合和B集合,然后A中一些人认识B中的一些人,但是它们集合内部互不认识,现在要找,A集合和B集合中互不认识的人有多少个?

那么求出来最大匹配数后,按照我第二个思想(二分图最小点覆盖),用总定点数减去最大匹配数后就是互不认识的人,那就是最大独立子集=顶点个数-最小顶点覆盖(最大二分匹配数),那么把路径看成一个集合就能理解了。

另外如果最小路径上可以有点重复,需要floyd缩点,不怎么懂,稍微看懂点的博客

 

1.百度一下“字典树 博客”,第一页的那个能看懂看那个,主要是思想+代码

2.入门题hdu1671

注意释放内存

代码

#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct tree
{
    tree *next[10];
    int f;
    int v;
};
char s[1005];
int flag;
tree *root;
void creat(char *str)
{
    int len=strlen(str);
    tree *p=root,*q;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(p->next[id]==NULL)
        {
            q=new tree;
            for(int i=0;i<=9;i++)
                q->next[i]=NULL;
            q->f=0;
            q->v=0;
            p->f=1;
            p->next[id]=q;
            p=q;
        }
        else
        {
            p=p->next[id];
            if(p->v==-1)
                flag=1;
        }
    }
    p->v=-1;
    if(p->f)
    {
        flag=1;
    }
}
void deal(tree *T)
{
    for(int i=0;i<=9;i++)
        if(T->next[i]!=NULL)
        deal(T->next[i]);
    delete T;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        root=new tree;
        for(int i=0;i<=9;i++)
        {
            root->next[i]=NULL;
        }
        root->f=0;
        root->v=0;
        memset(s,0,sizeof(s));
        int n;
        scanf("%d",&n);
        getchar();
        flag=0;
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            creat(s);
        }
        if(flag)
            printf("NO\n");
        else
            printf("YES\n");
            deal(root);
    }
    return 0;
}