URAL 1099

#include <algorithm>
#include <cstdio>
#include <deque>
using namespace std;

const int N = 222;
bool a[N][N] = {}, flag[N], in[N];
int n, block[N], mate[N], path[N];
deque<int> q;

void Modify(int u, int lca)
{
    while (block[u] != lca)
    {
        int v = mate[u];
        flag[block[u]] = tru

Hungarian Algorithm with DFS & BFS && Hopcroft-Karp Algorithm && Kuhn-Munkres Algorithm

这里假定二分图G（X，Y，E）中|X|=|Y|（两边点数相同，都为n）

Hungarian with DFS

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1000;
bool flag[N];
int mate[N];
vector<int> g[N];

bool DFS(int x)
{
    for (vector<int>::cons

你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？

众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼·布德曼·T.D.·柠檬·1900，朋友们都叫他1900。

1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上。很不幸，他刚出生就被抛弃，成了孤儿。1900孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他。

可能是天使的点化，190

不知道是不是叫作 Shortest Augmenting Path
采用 gap heuristic 优化

#include <algorithm>
#include <cstdio>
using namespace std;

int h[1024], hn[1025], n;
struct edge
{
    int v, c;
    edge *next, *rev;
    edge() {}
    edge(int v, int c, edge *next) : v(v), c(c), next(next) {}
    void *operator new(size_t, void *p)
  

<Introduction to Algorithms> 中的一道习题
一个包含 n 个 insert 和 m 个 extract-min 操作的序列
insert，插入一个数，这个数来自于域 (1,2,……,n}，，保证每次插入的数互不相同
extract-min，从当前插入且未删除的数中选择最小的输出，然后把这个数删除
希望对一个数组 extracted[1..m] 进行填充，使得 extracted[i] 存放第 i 次 extract-min 操作的结果

比如：
3,5,E,1,2,E,E,E,4,E（整数代表 insert 操作，E 表示 extract-min 操作）

extracted[1..5] 应为
3,1,2,5,4

求 TSP 问题的近似最优解

#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

const int N = 51;
const int M = 20; //蚂蚁数量
const int Q = 100;
const int ALPHA = 1;
const int BETA = 4;
const int TIMES = 200; //迭代次数
const double RHO = 0.3; //信息素的散逸系数
int best_path[N], //最优路径
   path[N]; //当前路径
double best_

Double-Ended Heap（Deap，双端堆）是一种 double-ended priority queue（双端优先队列），它是最小堆和最大堆的结合体，即既支持获取最小关键字的操作，又能获取最大关键字，并能进行删除。它的根是一个没有关键字的结点，左边是一个最小堆，右边是一个最大堆。它的高度的界为 Θ(log n)，插入、删除关键字的时间复杂度均为 Ο(log n)。

下面是 Double-Ended Heap 的实现：

#include <vector>

template <typename Type>
class DoubleEndedHeap
{
public:
   

Red-Black Tree（红黑树）是一种自平衡二叉查找树，它在1972年由 Rudolf Bayer 发明，他称之为 “Symmetric Binary B-Tree”。Leo J. Guibas 和 Robert Sedgewick 在1978年写的一篇论文中 把它命名为“Red-Black Tree”。它有良好的最坏情况下的运行时间，实践中也非常高效。它可以在 Ο(log n) 的时间内查找、插入、删 除。很多版本的 C++ STL 中使用了 Red-Black Tree。
一颗 Red-Black Tree 中的每个结点都带有颜色域，可以是红色或黑色（正如它的名字）。除了二叉搜索树的基本要求外，还有如下要求：
1

#include <stdio.h>
char a = '\\', b = '\n', c = '"', *p = "#include <stdio.h>%cchar a = '%c%c', b = '%cn', c = '%c', *p = %c%s%c;%cint main() {printf(p,b,a,a,a,c,c,p,c,b); }";
int main() {printf(p,b,a,a,a,c,c,p,c,b); }

写得这么复杂，就是为了能跨不同的字符集