noip板子

倍增法lca

const int N = 500010;
int n, m, s;
vector<int> g[N];
void addeg(int u, int v) {g[u].push_back(v);g[v].push_back(u);
}int d[N], anc[N][25];
void dfs(int u, int fa) {d[u] = d[fa] + 1;for (int i : g[u]) {if (i == fa) continue;anc[i][0] = u;dfs(i, u);}
}
void initlca() {for (int i = 1; i <= 21; ++i) {for (int j = 1; j <= n; ++j) {anc[j][i] = anc[anc[j][i-1]][i-1];}}
}
int qry(int u, int v) {if (d[u] < d[v]) swap(u, v);for (int i = 21; i >= 0; i --) {if (d[anc[u][i]] >= d[v]) {u = anc[u][i];}}if (v == u) return v;for (int i = 21; i >= 0; i --) {if (anc[v][i] != anc[u][i]){v = anc[v][i];u = anc[u][i];}}return anc[u][0];
}

Kruakal求最小生成树

const int N = 5010, M = 200010;
struct eg {int u, v, w;
} es[M];
bool cmp(eg a, eg b) {return a.w < b.w;}
int f[N], n, m;
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);
}
int cnt, ans;
void kruskal() {sort(es+1, es+m+1, cmp);for (int i = 1; i <= m; i ++) {int u = find(es[i].u), v = find(es[i].v);if (u == v) continue;ans += es[i].w;f[u] = v;cnt++;}
}

Dijkstra

const int N = 100010;
struct nd {int u, dis;bool operator<(const nd &a) const {return dis > a.dis;}
};
struct eg {int v, w;
};
priority_queue<nd> q;
vector<eg> g[N];
int n, m, dis[N], s;
bool vis[N];
void addeg(int u, int v, int w) {g[u].push_back((eg){v, w});
}
void dij(){fill(dis+1, dis+n+1, INT_MAX);dis[s] = 0;q.push((nd){s, 0});while (!q.empty()) {nd now = q.top(); q.pop();if (vis[now.u]) continue;vis[now.u] = 1;for (eg i : g[now.u]) {if (dis[i.v] > (i64)dis[now.u] + i.w) {dis[i.v] = dis[now.u] + i.w;q.push((nd){i.v, dis[i.v]});}}}
}