BurNingZz-CSDN博客

原创 KMP,扩展KMP模板

KMP算法#include #include using namespace std; /* P为模式串，下标从0开始 */ void GetNext(string P, int next[]) { int p_len = P.size(); int i = 0; //P的下标 int j = -1; next[0] = -1; while (i

2017-09-04 09:36:39 512

原创 POJ 2528 Mayor's posters 线段树+离散化

这题的题意是在一段线段上贴海报，给了贴的顺序和海报覆盖的区域，问最后能看见的海报个数。首先后面贴的海报能覆盖前面的海报，所以我们从后面开始贴，如果贴的区域之前已经被覆盖了就说明这个海报不可能被看见，否则数量+1。由于线段长度范围很大，但是海报的数量只有10000，所以应该对数据进行离散化。 The citizens of Bytetown, AB, could not

2017-09-01 15:47:01 260

原创 HDU 1161 敌兵布阵线段树单点更新

线段树入门题，单点更新，区间查询。 C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视

2017-09-01 15:43:28 353

原创 POJ 3281 Dining 网络流

这题的关键是如何建边。图的顶点是食物所对应的匹配中的食物和牛，饮料对应的匹配中的饮料和牛，源点s，汇点t 食物匹配和饮料匹配中相同的牛之间连一条边，这样可以确保一头牛不会分配多组食物和饮料。边：s->食物->牛->牛->饮料->t Cows are such finicky eaters.

2017-09-01 15:12:32 465

原创 POJ 3026 Borg Maze 最小生成树+BFS

先用BFS求出点与点之间的距离，然后用kruskal算法求出答案 The Borg is an immensely powerful race of enhanced humanoids from the delta quadrant of the galaxy. The Borg collective is the term used to describe the group

2017-09-01 15:07:36 377

原创 HDU 1281 棋盘游戏二分匹配匈牙利算法

这题是二分图匹配问题，把X坐标作为左边的点，Y坐标作为右边的点，然后进行匹配。至于求重要点，只需要遍历每个点，把该点对应的边去掉，然后进行匹配，看是否等于最大匹配值，如果不是的话说明该点是重要点。小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但

2017-09-01 14:59:55 472

原创一般图匹配带花树模板

#include #include #include #include #include #include using namespace std; #define MAXE 250*250*2 #define MAXN 250 #define SET(a,b) memset(a,b,sizeof(a)) deque Q; //g[i][j]存放关系图：i,j是否有边,match[i]

2017-09-01 10:47:47 306

BurNingZz的博客