模板整理、部分知识点文章上传至 Github
二分（返回第一个等于x的元素的下标）
int found(int a[],int left,int right,int x) {
while (left < right) {
int mid = (right + left) >> 1;
if (a[mid] < x) left = mid + 1;
else right = mid;
}
return left;
}
并查集
int f[maxn];
void init() { for (int i = 1; i <= n; ++i)f[i] = i; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) f[y] = x;
}
...
链式前向星
struct Edge {
int next, to;
LL dis;
}edges[maxn];
void add_edge(int from, int to, LL dis) {
num++;
edges[num].next = head[from];
edges[num].to = to;
edges[num].dis = dis;
head[from] = num;
}
for (int i = head[u]; i != 0; i = edges[i].next) {
...
}
邻接矩阵
struct Edge {
int from, to, dist;
//边的起点，终点，长度
Edge(int u,int v,int d):from(u),to(v),dist(d){}
//构造函数，用于边的初始化
};
struct HeapNode {
int d, u;//将结点的d值与结点捆绑在一起形成结构体，当然也可以用pair<int,int>代替
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
//当d>rhs.d为真时，优先级this<rhs.d成立，即d值小的优先级更大
}
};
void init(int n) {//初始化
num=0;//边在vector中的编号
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
//个人习惯，为了计数都能从1开始，先塞一个无关紧要的元素
edges.push_back(Edge(0, 0, 0));
//但G[i]计数还是从0开始
}
void AddEdge(int from, int to, int dist) {
edges.push_back(Edge(from, to, dist));
//调用Edge结构体中的构造函数，生成一条边并加入到Edge中
G[from].push_back(++num);
}
拓扑排序
int n, m, head[N], tot, deg[N], cnt;
vector<int>a;
struct node {
int v, next;
}e[N << 1];
void add(int u, int v) {
e[++tot].v = v;
e[tot].next = head[u];
head[u] = tot;
deg[v]++;//入度
}
void topsort() {
queue<int>q;
for (int i = 1; i <= n; ++i)
if (deg[i] == 0)q.push(i);
while (q.size()) {
int x = q.front(); q.pop();
a[++cnt] = x;
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].v;
if (--deg[y] == 0)q.push(y);
}
}
}
int main() {
cin >> n >> m;//点数、边数
for (int i = 1; i <= m; ++i) {
int x, y;//有向边
cin >> x >> y;
add(x, y);
}
topsort();
for (int i = 1; i <= a.size(); ++i)
cout << a[i] << " ";
cout << endl;
}
最短路（Floyd）
//初始化
for (int i = 0;i < maxn ; i++) for (int j = 0;j< maxn ; j++)
d[i][j] = (i == j) ? 0 : INF;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//传递闭包
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] |= d[i][k] & d[k][j];
最短路（SPFA）
int cnt[maxn];
bool inq[maxn];
int d[maxn];
bool spfa(int s) {
queue<int>Q;
memset(inq, 0, sizeof(inq));//标记结点是否在队列中
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; i++) d[i] = INF;
d[s] = 0; inq[s] = true;//标记结点s已在队列中
Q.push(s);//入队
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;//标记已不在队列
for (int i = 0; i < G[u].size(); i++) {
Edge& e = Edges[G[u][i]];//遍历以结点u为起点的有向边
if (d[u]<INF && d[u] + e.dist<d[e.to]) {
d[e.to] = d[u] + e.dist;//松弛
p[e.to] = G[u][i];//记录父节点
if (!inq[e.to]) {//只要不在队列中就可以入队
Q.push(e.to);
inq[e.to] = true;
if (++cnt[e.to] > n) return false;
//如果某个点迭代了超过n次，说明存在可以无限缩短的最短路，即负环
}
}
}
}
return true;
}
最短路（朴素Dijkstra）
int dis[maxn];
bool vis[maxn];
void dijkstra()
{
/*
memset(vis,false);
memset(dis,inf);
*/
for (int i = 1; i <= n; i++) dis[i] = inf, vis[i] = 0, a[i][i] = 0; //初始化各数组
dis[s] = 0; vis[s] =true;//s作为起点
for (int i = 1; i < n; i++) //重复n-1次
{
int x = -1;//寻找的最小边点
for (int j = 1; j <= n; j++)
if (!vis[j] && (x == 0 || dis[j] < dis[x])) //寻找未访问过且离起点最近的点
x = j;
if(x == -1) break;
vis[x] = 1;
for (int y = 1; y <= n; y++) //第一轮dis[y]中由起点可到达的点得到更新
dis[y] = min(dis[y], dis[x] + a[x][y])
}
}
最短路（堆优化Dijkstra）
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int inf = 2147483647;
const int manx = 1e4 + 5; //与n相对，对应顶点的个数
const int mamx = 5e5 + 5; //与m相对，对应边的个数
priority_queue< pair<int, int> >q;
struct node {
int next, v, w;
}edge[mamx]; //边取mamx，其余取manx
bool vis[manx]; //这里的标记数组与spfa的vis数组含义不同，这里标记是否入过队列
int head[manx], d[manx];
int k = 0;//tot 总边数
int n, m, s, e; //s作为起点，e作为终点
void add(int u, int v, int w) {//邻接表存储
edge[++k].next = head[u];
edge[k].v = v;
edge[k].w = w;
head[u] = k;
}
void dijkstra()
{
for (int i = 1; i <= n; i++) //初始化vis d 数组
d[i] = inf, vis[i] = 0;
d[s] = 0; //s作为起点
q.push(make_pair(0, s));
while (q.size()) {
int x = q.top().second; //取出队头
q.pop();
if (vis[x]) continue; //如果点x访问过，跳过，访问下一个队头
vis[x] = 1; //访问x做标记
for (int i = head[x]; i; i = edge[i].next) {
int v = edge[i].v, w = edge[i].w;
if (d[v] > d[x] + w) { //松弛操作，更新距离
d[v] = d[x] + w;
q.push(make_pair(-d[v], v)); //把更新的距离和点入队，这里距离取负变成小根堆
}
}
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
//无向图 add(v,u,w);
}
s = 1;
dijkstra();
for (int i = 1; i <= n; i++)
printf("%d ", d[i]);
return 0;
}
最小生成树（Kruskal）
#include<bits/stdc++.h>
using namespace std;
struct rec { int x, y, z; }edge[500010];
int fa[100010], n, m, ans;
bool cmp(rec a, rec b) {
return a.z < b.z;
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
//并查集初始化
for (int i = 1; i <= n; ++i)fa[i] = i;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> edge[i].x >> edge[i].y >> edge[i].z;
//按照边权排序
sort(edge + 1, edge + 1 + n, cmp);
//求最小生成树
for (int i = 1; i <= m; ++i) {
int x = find(edge[i].x);
int y = find(edge[i].y);
if (x == y) continue;
fa[x] = y; //如果不在同一个集合,总权值更新,并且集合和并
ans += edge[i].z;
}
cout << ans << endl;
}
最小生成树（Prim）
const int inf=2147483647;
int a[manx][manx], d[manx], n, m, ans;
bool vis[manx];
void prim(){
for(int i=1;i<=n;i++) d[i]=inf,vis[i]=0,a[i][i]=0; //初始化各数组
d[1]=0; //1作为起点
for(int i=1;i<n;i++) //重复n-1次
{
int x=0;
for(int j=1;j<=n;j++)
if( !vis[j] && (x==0||d[j]<d[x]) ) //寻找未访问过且离集合S最近的点
x=j;
vis[x]=1;
for(int y=1;y<=n;y++) //第一轮d[y]中由起点可到达的点得到更新
d[y]=min( d[y ], a[x][y]) //这里与Dij不同，因为Dij求的是两点间的距离，而这里是点到集合距离
}
}
强连通分量（korasaju 算法）
int V; // 顶点数
vector<int> G[maxn]; // 图的邻接表表示
vector<int> rG[maxn]; // 反向图
vector<int> vs; // 后序遍历顺序的顶点列表
bool book[maxn]; // 访问标记
int cmp[maxn]; // 所属强连通分量的拓补序
void dfs(const int& v) {
book[v] = true;
for (int i = 0; i < G[v].size(); ++i)
if (!book[G[v][i]])dfs(G[v][i]);
vs.push_back(v);
}
void rdfs(const int& v, const int& k) {
book[v] = true; cmp[v] = k;
for (int i = 0; i < rG[v].size(); ++i)
if (!book[rG[v][i]])rdfs(rG[v][i], k);
}
//korasaju 算法核心：双重DFS标记
int scc() {
ms(book, false); vs.clear();
for (int v = 0; v < V; ++v)
if (!book[v])dfs(v);
ms(book, false); int k = 0;
for (int i = vs.size() - 1; i >= 0; --i)
if (!book[vs[i]])rdfs(vs[i], k++);
return k;//k为连通分量的个数
}
强连通分量（Tarjan 算法）
线段树
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 10;
struct Node {
int l, r, val;
int sum;
int lmax, rmax, dat;
//不能简单的对比对比左右子区间的dat和值(区间最大和值)来更新本节点的区间最大和值，还要对比右子树的rmax+左子树的lmax的和值
}node[maxn << 2];
int n, m;
int a[maxn];
void pushdown(int rt) {
node[rt].sum = node[rt << 1].sum + node[rt << 1 | 1].sum;
node[rt].lmax = max(node[rt << 1].lmax, node[rt << 1].sum + node[rt << 1 | 1].lmax);
node[rt].rmax = max(node[rt << 1 | 1].rmax, node[rt << 1 | 1].sum + node[rt << 1].rmax);
node[rt].dat = max(node[rt << 1].dat, node[rt << 1 | 1].dat);
node[rt].dat = max(node[rt].dat, node[rt << 1].rmax + node[rt << 1 | 1].lmax);
}
//构建线段树，完成区间和，区间max，dat的更新
void build(int rt, int l, int r) {
node[rt].l = l, node[rt].r = r;
if (l == r) {
node[rt].val = node[rt].lmax = node[rt].rmax = node[rt].dat = a[l];
node[rt].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r);
pushdown(rt);
return;
}
Node query(int rt, int l, int r) {
if (l <= node[rt].l && node[rt].r <= r) {
return node[rt];
}
Node t1, t2, ans;
t1.dat = t1.sum = t1.lmax = t1.rmax = t2.dat = t2.sum = t2.lmax = t2.rmax = -inf;
int mid = (node[rt].l + node[rt].r) >> 1;
if (l <= mid) t1 = query(rt << 1, l, r), ans.sum += t1.sum;
if (r > mid) t2 = query(rt << 1 | 1, l, r), ans.sum += t2.sum;
ans.dat = max(max(t1.dat, t2.dat), t1.rmax + t2.lmax);
ans.lmax = max(t1.lmax, t1.sum + t2.lmax);
ans.rmax = max(t2.rmax, t2.sum + t1.rmax);
if (l > mid) ans.lmax = max(ans.lmax, t2.lmax);
if (r <= mid) ans.rmax = max(ans.rmax, t1.rmax);
return ans;
}
void update(int rt, int pos, int val) {
if (node[rt].l == pos && node[rt].l == node[rt].r) {
node[rt].sum = node[rt].val = val;
node[rt].lmax = node[rt].rmax = node[rt].dat = val;
return;
}
int mid = (node[rt].l + node[rt].r) / 2;
//cout<<pos<<" "<<rt<<" "<<mid<<endl;
if (pos <= mid) update(rt << 1, pos, val);
else update(rt << 1 | 1, pos, val);
pushdown(rt);
}
int main() {
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
int op, l, r;
while (m--) {
cin >> op >> l >> r;
if (op == 1) {
if (l > r) swap(l, r);
cout << query(1, l, r).dat << endl;//根据需要输出不同的
}
else {
update(1, l, r);
}
}
return 0;
}
树状数组
int n;
int a[1005],tree[1005]; //原数组和树状数组
int lowbit(int x) return x&(-x); //取出x的最低位1
//修改
void updata(int i,int p){ //在i位置加上p
while(i <= n){
tree[i] += p;//更新受影响的tree[i]
i += lowbit(i);
}
}
//查询
int getsum(int i){//求区间1到i的和
int res = 0;
while(i > 0){
res += tree[i];
i -= lowbit(i);
}
return res;
}
高级操作：
二维树状数组：①单点修改，区间查询 ②区间修改，区间查询
二分图：匈牙利算法
int M, N; //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN]; //记录当前右侧元素所对应的左侧元素
bool vis[MAXN]; //记录右侧元素是否已被访问过
bool match(int i)
{
for (int j = 1; j <= N; ++j)
if (Map[i][j] && !vis[j]) //有边且未访问
{
vis[j] = true; //记录状态为访问过
if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
{
p[j] = i; //当前左侧元素成为当前右侧元素的新匹配
return true; //返回匹配成功
}
}
return false; //循环结束，仍未找到匹配，返回匹配失败
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= M; ++i)
{
memset(vis, 0, sizeof(vis)); //重置vis数组
if (match(i))
cnt++;
}
return cnt;
}
数位DP
LL dp[20][][];
//维数视情况决定，比如在【不要62】中，dp状态要区分有没有6
int a[20];
//给出数字范围在10^18以内可用，位数更多就扩大一下
LL dfs(int pos,bool lead,bool limit){
//pos当前枚举的位置，lead有无前导零，limit有无最高位限制
LL ans = 0;
if (pos == -1) return 1;
if (!limit && !lead && dp[pos] != -1) return dp[pos];
//无前导零和最高位限制才能使用已储存的状态
int end = limit ? a[pos] : 9;
for (int i = 0; i <= end; i++) {
if (不合法的情况（除0以外）) continue;
if (!lead && (!i)) continue;
//当前位为是零但不是前导零，也不合法，跳过（如果0不合法的话）
ans += dfs(pos - 1, lead&&(!i), limit && i == end);
//当前位是合法情况，继续搜
}
if (!limit&&!lead) dp[pos] = ans;
//没有前导零也没有最高位限制，说明本次统计结果是通用的
return ans;
}
LL part(LL x){
int len = 0; LL k = x;
while (k) { a[len++] = k % 10; k /= 10; }
memset(dp, -1, sizeof (dp));
return dfs(len - 1, true, true);
//如果涉及到前导零，一般刚开始时都是默认有的
}
//注意l=0的时候不能用，要特判
LL result(LL l , LL r) {
return part(r) - part(l-1);
}
LCA（倍增）
int num = 0;
int head[maxn], depth[maxn], lg[maxn], fathers[maxn][20];
struct Edge {
int next, to;
}edges[2 * maxn];
void add_edge(int u, int v) {
num++;
edges[num].to = v;
edges[num].next = head[u];
head[u] = num;
}
void dfs(int u, int u_father) {
depth[u] = depth[u_father] + 1;
fathers[u][0] = u_father;
for (int i = 1; (1 << i) <= depth[u]; i++)
fathers[u][i] = fathers[fathers[u][i - 1]][i - 1];
for (int i = head[u]; i; i = edges[i].next) {
if (edges[i].to != u_father) dfs(edges[i].to, u);
}
}
int LCA(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
while (depth[u] > depth[v])
u = fathers[u][lg[depth[u] - depth[v]] - 1];
if (u == v) return u;
for (int k = lg[depth[u]] - 1; k >= 0; k--) {
if (fathers[u][k] != fathers[v][k]) {
u = fathers[u][k];
v = fathers[v][k];
}
}
return fathers[u][0];
}
int main(){
dfs(1, 0);
//常数优化
for (int i = 1; i <= n; i++) {
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
}
LCA（树剖）
int num = 0;
int head[maxn], depth[maxn], siz[maxn], dad[maxn], top[maxn];
//top[i]：节点i所在重链的链头
struct Edge {
int next, to;
}edges[2 * maxn];
void add_edge(int u, int v) {
num++;
edges[num].to = v;
edges[num].next = head[u];
head[u] = num;
}
void getDepth(int now) {
siz[now] = 1;
depth[now] = depth[dad[now]] + 1;
for (int i = head[now]; i != 0; i = edges[i].next) {
int v = edges[i].to;
if (v != dad[now]) {
dad[v] = now;
getDepth(v);
siz[now] += siz[v];
}
}
}
void getLink(int x) {
int t = 0;
if (!top[x]) top[x] = x;
for (int i = head[x]; i != 0; i = edges[i].next) {
int v = edges[i].to;
if (v != dad[x] && siz[v] > siz[t]) t = v;
}
if (t) {
top[t] = top[x];
getLink(t);
}
for (int i = head[x]; i != 0; i = edges[i].next) {
int v = edges[i].to;
if (v != dad[x] && t != v) getLink(v);
}
}
int LCA(int u, int v) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) swap(u, v);
u = dad[top[u]];
}
//直到u和v位于同一条重链上
return (depth[u] < depth[v]) ? u : v;
//深度更小的那一个就是公共祖先
}
int main()
{
// ios::sync_with_stdio(false);
// int t; cin >> t; while (t--) {
int n, m;
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
getDepth(1);
getLink(1);
return 0;
}
康托展开&逆康托展开
const int FAC[] = { 1,1,2,6,24,120,720,5040,40320,362880,3628800 };
int cantor(int* a) {//算出全排列对应的哈希值
int x = 0;
for (int i = 0; i < 9; i++) {
int smaller = 0;
for (int j = i + 1; j < 9; j++) {
if (a[j] < a[i]) smaller++;
}
x += FAC[9 - i - 1] * smaller;
}
return x+1;
//注意全排列数组a是从零开始的
}
void decantor(int x,int*ans) {//x哈希值，n数字个数，a算出的全排列
x--;
vector<int> v;
for (int i = 1; i <= 9; i++) v.push_back(i);
for (int i = 0; i < 9; i++) {
int r;
r = x / FAC[9 - i - 1];
x = x % FAC[9 - i - 1];
sort(v.begin(), v.end());
ans[i] = v[r];
v.erase(v.begin() + r);
}
//注意算出的全排列数组ans是从0开始的
}