最小表示法:

const int MAXN = 1000010;

int n;

char S[MAXN];

int min_position()

}

筛素数法：

const int MAXN = 1000010;

int n;

bool flag[MAXN];

vector<int> V;

void get_prime()

}

快速幂：

int power(int x, int n, int m)

}

扩展欧几里得：

int S, m, m1, r1, m2, r2;

int x, y, z;

int extend_gcd(int a, int b)

}

int g = extend_gcd(m1, m2);

x = ((r2 - r1) / g * x % (m2 / g) + (m2 / g)) % (m2 / g);

S = x * m1 + r1;

m = m1 * m2 / g;

图论

1.Bellman_ford:

Vector<int> V[MAXN], W[MAXN];

Bool bellman_ford(int n)

}

2.Prim:

int dis[MAXN];

bool visit[MAXN];

int k, H[MAXN], V[MAXE], W[MAXE], N[MAXE];

vector<int> T;

void prim(int x)

}

3.Tarjan 算法

一：求强连通分量(有向图，有inS数组记录)、双连通分量、割边、割点(无向图，无inS数组记录)

bool inS[MAXN];

int t, n, m;

int top, S[MAXN];

int inx, low[MAXN], dfn[MAXN];

int s, belong[MAXN], degree[MAXN];

vector<int> maps[MAXN];

void tarjan(int u, int p)

}

int main()

}

4.LCA:

一：<n * log(n), sqrt(n)>算法:分为sqrt(n)层，分别处理(用于数据较少情况)

bool visit[MAXN];

int n, k, W[MAXN], V[MAXN];

int h, m, P[MAXN], D[MAXN], S[MAXN];

vector<int> maps[MAXN], edge[MAXN];

void prepare_dfs(int u, int e)

}

void get_level_dfs(int u)

}

void prepare()

}

int LCA(int a, int b)

}

二．<n * log(n), log(n)>增量法:

bool visit[MAXN];

int n, k, W[MAXN], V[MAXN];

int P[MAXN], D[MAXN], S[MAXN][MAXLOG];

vector<int> maps[MAXN], edge[MAXN];

void prepare_dfs(int u, int e)

}

void prepare()

}

int LCA(int a, int b)

}

三．Tarjan的LCA算法(离线算法，首先要记录下所有的询问，然后再一次tarjan得到所有的答案。)

bool visit[MAXN];

int n, P[MAXN];

vector<int> maps[MAXN], Q[MAXN];

int find_set(int e)

}

void union_set(int a, int b)

}

void tarjan(int u)

}

RMQ:

void RMQ()

{

for (int i = 1; i <= n; ++ i)

RMQ[i][0] = S[i];

for (int k = 1; (1 << k) <= n; ++ k)

for (int i = 1; i <= n - (1 << k) + 1; ++ i)

RMQ[i][k] = max(RMQ[i][k - 1], RMQ[i + (1 << (k - 1))][k - 1]);

for (int i = 1; i <= m; ++ i)

{

int k = log(b - a + 1.0) / log(2.0);

ans = max(RMQ[a][k], RMQ[b - (1 << k) + 1][k]);

}

}

网络流：

一． 最大流

1. Edmonds-Karp算法

int n, m;

int pre[MAXN], min_flow[MAXN];

int maps[MAXN][MAXN], flow[MAXN][MAXN];

int edmonds_karp()

}

2.dinic算法(未分层)：

bool visit[MAXN];

bool flag[MAXN][MAXN];

int front, rear, Q[MAXN];

int S, T, maps[MAXN][MAXN];

bool bfs()

}

int dfs(int u, int w)

}

int Dinic()

}

3.dinic算法(分层)：

int S, T, D[MAXN];

int front, rear, Q[MAXN];

int inx, H[MAXN], V[MAXE], W[MAXE], N[MAXE];

void add_edge(int u, int v, int w)

}

void build_maps()

}

bool dinic_bfs()

}

int dinic_dfs(int u, int w)

}

int dinic()

}

4.push_relable：

queue<int> Q;

int S, T, D[MAXN], flow[MAXN];

int inx, H[MAXN], V[MAXE], W[MAXE], N[MAXE];

int push_relabel()

}

5．sap算法(递归版本)：

int n, S, T, D[MAXN], G[MAXN];

int inx, H[MAXN], V[MAXE], W[MAXE], N[MAXE];

int sap_dfs(int u, int w)

}

int sap()

}

6．sap算法(非递归版本)：

int sap(int n)

}

7. 欧拉路径(最大流解混合图的欧拉回路问题)

1 定义

欧拉通路 (Euler tour)——通过图中每条边一次且仅一次，并且过每一顶点的通路。

欧拉回路 (Euler circuit)——通过图中每条边一次且仅一次，并且过每一顶点的回路。

欧拉图——存在欧拉回路的图。

2 无向图是否具有欧拉通路或回路的判定

G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。

G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。

3 有向图是否具有欧拉通路或回路的判定

D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。

D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。

4 混合图。混合图也就是无向图与有向图的混合，即图中的边既有有向边也有无向边。

5 混合图欧拉回路

混合图欧拉回路用的是网络流。

把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。

现在每个点入度和出度之差均为偶数。将这个偶数除以2，得x。即是说，对于每一个点，只要将x条边反向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。

现在的问题就变成了：该改变哪些边，可以让每个点出 = 入？构造网络流模型。有向边不能改变方向，直接删掉。开始已定向的无向边，定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。

由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。

所以，就这样，混合图欧拉回路问题，解了。

二分图匹配：

bool visit[MAXN];

int n, m, match[MAXN];

vector<int> maps[MAXN];

bool dfs(int u)

}

int ans = 0;

memset(match, -1, sizeof(match));

for (int i = 1; i <= n; ++ i)

{

memset(visit, 0, sizeof(visit));

if (dfs(i))

++ ans;

}

最长上升子序列(LIS)：

vector<int> S;

int get_lis(int n)

}

计算几何

1. 交点的无斜率求法

Point interact(const Point &A, const Point &B, const Point &C, const Point &D)

}

数论

1. 两个数p, q，如果gcd(p, q) == 1，那么当x,y为正整数时，px + qy最大不能表示的数是pq – p – q, 若gcd(p, q) != 1，那么为无穷大。

2.欧拉函数：

欧拉定理：设m > 1, gcd(a, m) == 1, 则a^φ(m) % m == 1;

费马小定理：若p为素数，则a^p % p == a;

int Eluar(int n)

}

3.海伦公式:

假设有一个三角形，边长分别为，三角形的面积 可由以下公式求得：

S = sqrt(p * (p – a) * (p – b) * (p – c))，

这里, p = (a + b + c) / 2;

4.Polya：

N = (A1 + A2 + … + Am) / m;

其中，Ai指第i种置换的方式，n指置换方式的总数。

Ai形如： X1^a1 * X2^a2 * X3 * … * Xm^am，m为物品总数，a1,a2…am分别为循环长度为1, 2, ..m的环的个数。

旋转的情况中，当旋转的个数k时，循环节的个数为gcd(k, N).

5.贝祖等式

对于等式ax+by=z，若c为a,b的最大公约数，等式有整数解当且仅当z为c的倍数。

Dancing links

1.精确覆盖

void remove(const int c)

{

L[R[c]] = L[c];

R[L[c]] = R[c];

for (int i = D[c]; i != c; i = D[i])

for (int j = R[i]; j != i; j = R[j])

{

U[D[j]] = U[j];

D[U[j]] = D[j];

-- S[C[j]];

}

}

void resume(const int c)

}

bool dfs(const int k)

}

2.可重复覆盖

void remove(const int c)

}

void resume(const int c)

}

int cost()

}

bool dfs(const int k)

}

DP

1. 树上有限制的背包

有一些物品，若选择了v,就必须要选择u，这样就构成了一棵树。要求选择某些物品，使得消耗不大于C，总价值最大。

int n, m, c[maxn], w[maxn], dp[maxn][maxn];

vector<int> maps[maxn];

void dfs(const int u, const int e)

}

void solve()

}

博弈

1.Nim积

const int nim[2][2] = {0, 0, 0, 1};

const lint bit[] = {2, 4, 16, 256, 65536, 4294967296};

int nim_mult_power(int x, int y)

}

int nim_mult(int x, int y)

}