并查集

struct dsu {
private:// number of nodesint n;// root node: -1 * component size// otherwise: parentstd::vector<int> pa;
public:dsu(int n_ = 0) : n(n_), pa(n_, -1) {}// find node x's parentint find(int x) {return pa[x] < 0 ? x : pa[x] = find(pa[x]);}// merge node x and node y // if x and y had already in the same component, return false, otherwise return true// Implement (union by size) + (path compression)bool unite(int x, int y) {int xr = find(x), yr = find(y);if (xr != yr) {if (-pa[xr] < -pa[yr]) std::swap(xr, yr);pa[xr] += pa[yr];pa[yr] = xr; // y -> xreturn true;}return false;}// size of the connected component that contains the vertex xint size(int x) {return -pa[find(x)];}
};

最短路

namespace Dijkstra {
#define ll long longstatic constexpr ll INF = 1e18;int n, m; // 点数 边数struct edge {int to;  // 点ll val; // 边权edge(int to_ = 0, ll val_ = 0) :to(to_), val(val_) {}bool operator < (const edge& k) const { return val > k.val; }};vector<vector<edge>> g;void init() { // 建图操作需要根据题意修改cin >> n >> m;g.resize(n);for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;--u, --v;g[u].push_back(edge(v, w));}}ll dijkstra(int s, int t) { // 最短路vector<ll> dis(n, INF);vector<bool> vis(n, false);dis[s] = 0;priority_queue<edge> pq;pq.push(edge(s, 0));while (!pq.empty()) {auto top = pq.top();pq.pop();if (!vis[top.to]) {vis[top.to] = true;for (auto nxt : g[top.to]) {if (!vis[nxt.to] && dis[nxt.to] > nxt.val + dis[top.to]) {dis[nxt.to] = nxt.val + dis[top.to];pq.push(edge(nxt.to, dis[nxt.to]));}}}}return dis[t];}
#undef ll
}

最小生成树

struct edge {int u, v;int w;edge(int u_ = 0, int v_ = 0, int w_ = 0) :u(u_), v(v_), w(w_) {}bool operator< (const edge& k) const {return w < k.w;}
};
long long kruskal() { // kruskal算法 需要并查集int n, m;cin >> n >> m;dsu u(n);vector<edge> g(m);for (auto& i : g) {cin >> i.u >> i.v >> i.w;--i.u, --i.v;}sort(g.begin(), g.end());long long res = 0;for (auto i : g) {if (u.unite(i.u, i.v)) {res += i.w;}}return res;
}

最小树形图

namespace ZL {// a 尽量开大, 之后的边都塞在这个里面const int N = 100010, M = 100010, inf = 1e9;struct edge {int u, v, w, use, id;edge(int u_ = 0, int v_ = 0, int w_ = 0, int use_ = 0, int id_ = 0): u(u_), v(v_), w(w_), use(use_), id(id_) {}}b[M], a[2000100];int n, m, ans, pre[N], id[N], vis[N], root, In[N], h[N], len, way[M];// 从root 出发能到达每一个点的最小树形图// 先调用init 然后把边add 进去, 需要方案就getway, way[i] 为1 表示使用// 最小值保存在ansvoid init(int _n, int _root) { // 点数 根节点n = _n; m = 0; b[0].w = inf; root = _root;}void add(int u, int v, int w) {m++;b[m] = edge(u, v, w, 0, m);a[m] = b[m];}int work() {len = m;for (;;) {for (int i = 1; i <= n; i++) { pre[i] = 0; In[i] = inf; id[i] = 0; vis[i] = 0; h[i] = 0; }for (int i = 1; i <= m; i++) {if (b[i].u != b[i].v && b[i].w < In[b[i].v]) {pre[b[i].v] = b[i].u; In[b[i].v] = b[i].w; h[b[i].v] = b[i].id;}}for (int i = 1; i <= n; i++) if (pre[i] == 0 && i != root) return 0;int cnt = 0; In[root] = 0;for (int i = 1; i <= n; i++) {if (i != root) a[h[i]].use++; int now = i; ans += In[i];while (vis[now] == 0 && now != root) { vis[now] = i; now = pre[now]; }if (now != root && vis[now] == i) {cnt++; int kk = now;while (1) {id[now] = cnt; now = pre[now];if (now == kk) break;}}}if (cnt == 0) return 1;for (int i = 1; i <= n; i++) if (id[i] == 0) id[i] = ++cnt;// 缩环, 每一条接入的边都会茶包原来接入的那条边, 所以要调整边权// 新加的边是u, 茶包的边是vfor (int i = 1; i <= m; i++) {int k1 = In[b[i].v], k2 = b[i].v;b[i].u = id[b[i].u];b[i].v = id[b[i].v];if (b[i].u != b[i].v) {b[i].w -= k1; a[++len].u = b[i].id; a[len].v = h[k2]; b[i].id = len;}}n = cnt; root = id[root];}return 1;}void getway() {for (int i = 1; i <= m; i++) way[i] = 0;for (int i = len; i > m; i--) { a[a[i].u].use += a[i].use; a[a[i].v].use -= a[i].use; }for (int i = 1; i <= m; i++) way[i] = a[i].use;}
}

最近公共祖先/倍增LCA

constexpr int SIZE = 200010;
constexpr int DEPTH = 21; // 最大深度 2^DEPTH - 1
int pa[SIZE][DEPTH], dep[SIZE];
vector<int> g[SIZE]; //邻接表
void dfs(int rt, int fin) { //预处理深度和祖先pa[rt][0] = fin;dep[rt] = dep[pa[rt][0]] + 1; //深度for (int i = 1; i < DEPTH; ++i) { // rt 的 2^i 祖先等价于 rt 的 2^(i-1) 祖先 的 2^(i-1) 祖先pa[rt][i] = pa[pa[rt][i - 1]][i - 1];}int sz = g[rt].size();for (int i = 0; i < sz; ++i) {if (g[rt][i] == fin) continue;dfs(g[rt][i], rt);}
}int LCA(int x, int y) {if (dep[x] > dep[y]) swap(x, y);int dif = dep[y] - dep[x];for (int j = 0; dif; ++j, dif >>= 1) {if (dif & 1) {y = pa[y][j]; //先跳到同一高度}}if (y == x) return x;for (int j = DEPTH - 1; j >= 0 && y != x; --j) { //从底往上跳if (pa[x][j] != pa[y][j]) { //如果当前祖先不相等 我们就需要更新x = pa[x][j];y = pa[y][j];}}return pa[x][0];
}

二分图最大权匹配/KM

namespace KM {typedef long long ll;const int maxn = 510;const int inf = 1e9;int vx[maxn], vy[maxn], lx[maxn], ly[maxn], slack[maxn];int w[maxn][maxn]; // 以上为权值类型int pre[maxn], left[maxn], right[maxn], NL, NR, N;void match(int& u) {for (; u; std::swap(u, right[pre[u]]))left[u] = pre[u];}void bfs(int u) {static int q[maxn], front, rear;front = 0; vx[q[rear = 1] = u] = true;while (true) {while (front < rear) {int u = q[++front];for (int v = 1; v <= N; ++v) {int tmp;if (vy[v] || (tmp = lx[u] + ly[v] - w[u][v]) > slack[v])continue;pre[v] = u;if (!tmp) {if (!left[v]) return match(v);vy[v] = vx[q[++rear] = left[v]] = true;} else slack[v] = tmp;}}int a = inf;for (int i = 1; i <= N; ++i)if (!vy[i] && a > slack[i]) a = slack[u = i];for (int i = 1; i <= N; ++i) {if (vx[i]) lx[i] -= a;if (vy[i]) ly[i] += a;else slack[i] -= a;}if (!left[u]) return match(u);vy[u] = vx[q[++rear] = left[u]] = true;}}void exec() {for (int i = 1; i <= N; ++i) {for (int j = 1; j <= N; ++j) {slack[j] = inf;vx[j] = vy[j] = false;}bfs(i);}}ll work(int nl, int nr) { // NL , NR 为左右点数, 返回最大权匹配的权值和NL = nl; NR = nr;N = std::max(NL, NR);for (int u = 1; u <= N; ++u)for (int v = 1; v <= N; ++v)lx[u] = std::max(lx[u], w[u][v]);exec();ll ans = 0;for (int i = 1; i <= N; ++i)ans += lx[i] + ly[i];return ans;}void output() { // 输出左边点与右边哪个点匹配, 没有匹配输出0for (int i = 1; i <= NL; ++i)printf("%d ", (w[i][right[i]] ? right[i] : 0));printf("\n");}
}

2-sat

/** 2-sat* n 表示限制个数, i 为取(真), i+n 为不取(假)* 先初始化再建图* 建图时 若输入两组或关系 ((x = a) || (y = b))则有:if (a && b) {Twosat::add(x + n, y), Twosat::add(y + n, x);} else if (!a && b) {Twosat::add(x, y), Twosat::add(y + n, x + n);} else if (a && !b) {Twosat::add(x + n, y + n), Twosat::add(y, x);} else {Twosat::add(x, y + n), Twosat::add(y, x + n);}* 表示若条件1/2不成立 则条件2/1必定成立* 构造结果保存在 ans 数组 若ans[i] = 0则取i 否则取i+n* */
namespace Twosat {const int M = 4000010, N = 1000010;struct edge {int next, point;edge(int n_ = 0, int p_ = 0) :next(n_), point(p_) {}} e[M];int n, len, now, sign, head, sign2;int p[N << 1], dfs[N << 1], low[N << 1], where[N << 1];int s[N << 1], in[N << 1], ans[N], out[N << 1];void add(int k1, int k2) {e[++len] = edge(p[k1], k2);p[k1] = len;}void init(int _n) {n = _n;for (int i = 0; i <= n * 2 + 1; i++) {p[i] = where[i] = dfs[i] = low[i] = s[i] = in[i] = out[i] = 0;}len = now = sign = head = sign2 = 0;}void tarjan(int k1) {s[++head] = k1; in[k1] = 1; dfs[k1] = ++sign; low[k1] = sign;for (int i = p[k1]; i; i = e[i].next) {int j = e[i].point;if (dfs[j] == 0) {tarjan(j);low[k1] = min(low[k1], low[j]);} else if (in[j]) {low[k1] = min(low[k1], dfs[j]);}}if (dfs[k1] == low[k1]) {now++;while (1) {where[s[head]] = now;in[s[head]] = 0;out[s[head]] = ++sign2;head--;if (s[head + 1] == k1) {break;}}}}int solve() { // ans[i] = 0 表示取i, 否则表示取i+nfor (int i = 1; i <= n * 2; i++) {if (dfs[i] == 0) {tarjan(i);}}for (int i = 1; i <= n; i++) {if (where[i] == where[i + n]) {return 0;}}for (int i = 1; i <= n; i++) {if (out[i] < out[i + n]) {ans[i] = 0;} else {ans[i] = 1;}}return 1;}
}

最大团/Bron-Kerbosch

/** 最大团 Bron-Kerbosch algorithm* 最劣复杂度 O(3^(n/3))* 采用位运算形式实现* */
namespace Max_clique {
#define ll long long
#define TWOL(x) (1ll<<(x))const int N = 60;int n, m;      // 点数 边数int r = 0;     // 最大团大小ll G[N];       // 以二进制形式存图ll clique = 0; // 最大团 以二进制形式存储void BronK(int S, ll P, ll X, ll R) { // 调用时参数这样设置: 0, TWOL(n)-1, 0, 0if (P == 0 && X == 0) {if (r < S) {r = S;clique = R;}}if (P == 0) return;int u = __builtin_ctzll(P | X);ll c = P & ~G[u];while (c) {int v = __builtin_ctzll(c);ll pv = TWOL(v);BronK(S + 1, P & G[v], X & G[v], R | pv);P ^= pv; X |= pv; c ^= pv;}}void init() {cin >> n >> m;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;--u, --v;G[u] |= TWOL(v);G[v] |= TWOL(u);}BronK(0, TWOL(n)-1, 0, 0);cout << r << ' ' << clique << '\n';}
}