二分匹配学习记录

二分匹配学习记录

参考资料

二分图讲解及匈牙利模板

HDU 2444

The Accomodation of Students

题意

给出图,求是否二分图,和二分图的最大匹配数。

思路

二分图BFS染色+最大匹配。

染色方法就是从起点开始染色,如果上一个点是白色,相邻点就染为黑色。直到碰到矛盾处,就可以知道不是二分图。

最大匹配是通过遍历所有的点,递归更新匹配来扩展匹配。

代码

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>......

KMP 学习记录

KMP 学习记录

kuangbin专题十六——KMP

KMP 学习总结

朴素 KMP 算法

void getNext(const char s[]){

int cur = 0, k = -1;

nxt[cur] = k;

while (cur < m) {

if (k == -1 || b[cur] == b[k])

nxt[++cur] = ++k;

else k = nxt[k];

}

}

int kmp(const char a[], const char b[]){

int......

排位赛 09 题解

排位赛 09 题解

A - Fox and Number Game

CodeForces - 389A

题意

给出一列数,数之间可以相减(大数-小数),不限次数,求这列数可以得到的最小总和。

思路

观察数据加上思考不难发现,每个数最后都可以变成同一个数,就是他们的最大公约数。

代码

#include <cstdio>

#include <algorithm>

using namespace std;

int main(){

int n, num[105];

scanf("%d", &n);

for (in......

AC自动机学习记录

AC自动机学习记录

参考资料

字典树(讲解+模版)

AC自动机算法

AC自动机算法详解

hdu 2222 ac自动机入门题

HDU 2222

Keywords Search

题意

给出一些模式串和一个主串,求主串中能匹配到的模式串数量。

思路

AC自动机裸题。

代码

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

#define LOCAL

const int kind = 26;

const int s_maxn = 50......

个人简介

王子恒,男,19岁。

热爱读书,热爱女毒,热爱游戏,热爱技术,但是只会摸鱼的死肥宅。

学过Python,Java,JavaScript,C++,但是依然只会摸鱼的菜鸡。

毕生最大愿望是活在梦里,以及吃香香鸡。