圖論模板（部分）
maincpp
#include <iostream>
#include <climits>
#include <limits>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);return 0;
}最短路
Dijkstra:
struct Node {int y, v; // 連到哪里 邊權Node(int _y, int _v) {y = _y; v = _v;};
};
int N; // 一共有多少個點
int n, m; // 多少個頂點 多少條邊
std::vector<int> dist(N + 1, MAX_INT); // 每個點最短路徑長度
std::vector<std::vector<Node>> edge(N + 1); // 1 ~ N
std::vector<bool> C(N + 1, false); // inline int dijkstra(int s, int t) { // 起點 終點std::fill(C.begin(), C.end(), false);std::fill(dist.begin(), dist.end(), MAX_INT);dist[s] = 0; // 初始化起點while(1) {int x = -1; // x 是不在C(點集)里面，并且離起點最近的那個點的下標for(int i = 1; i <= n; i++) { // 遍歷n個點if(!C[i] && dist[i] < 1 << 30) { // 如果點集C里面沒有這個點，并且能達到if(x == -1 || dist[i] < dist[x]) {x = i;}}}if(x == t || x == -1) break; // 如果說x到達了終點t或者沒有任何一個能達到的點就直接結束C[x] = true; // 加入到點集Cfor(const auto& i : edge[x]) dist[i.y] = std::min(dist[i.y], dist[x] + i.v); // 更新dist最小的點能達到的邊的值}return dist[t];}
Dijkstra (堆優化)：
std::vector<std::vector<PII>> e;
std::vector<int> dist;
std::vector<bool> vis;
std::priority_queue<PII, std::vector<PII>, std::greater<PII>> q;inline void Dijkstra() {q.push({0, s});dist[s] = 0;while(!q.empty()) {auto [val, u] = q.top();q.pop();if(vis[u]) continue;vis[u] = true;for(const auto&[v, w] : e[u]) {if(dist[v] > dist[u] + w) {dist[v] = dist[u] + w;q.push({dist[v], v});}}}}
SPFA:
struct Edge {int x, y, v;
};
int n, m, k;
std::vector<int> dist;
std::vector<Edge> edge;
std::vector<int> vis; // 標記節點是否在隊列中
std::vector<int> cnt; // 記錄每個節點入隊的次數，用于判斷負環inline void SPFA(int s, int t) {// 初始化距離數組std::fill(dist.begin(), dist.end(), INT_MAX);dist[s] = 0;// 初始化標記數組和入隊次數數組std::fill(vis.begin(), vis.end(), false);std::fill(cnt.begin(), cnt.end(), 0);std::queue<int> q;q.push(s);vis[s] = true;cnt[s]++;while (!q.empty()) {int u = q.front();q.pop();vis[u] = 0;rep(i, m) {if (edge[i].x == u) {int v = edge[i].y;int w = edge[i].v;if (dist[u] + w < dist[v]) {dist[v] = dist[u] + w;if (!vis[v]) {q.push(v);vis[v] = true;cnt[v]++;// 如果某個節點入隊次數超過 n 次，說明存在負環if (cnt[v] > n) {std::cout << "-1\n";return;}}}}}}// 輸出結果if (dist[t] < INT_MAX) std::cout << dist[t] << '\n';else std::cout << "-1\n";
}拓撲排序:
int n;
std::vector<std::vector<int>> e;
std::vector<int> d;
std::queue<int> q;inline void TopoSort(int x) {Rep(i, 1, n + 1) if(!d[i]) q.push(x);while(!q.empty()) {int u = q.front();q.pop();std::cout << u << '\n';for(const int& v : e[u]) {if(--d[v] == 0) {q.push(v);}}}
}
Floyd:
int n;
std::vector<std::vector<int>> f, e;
std::vector<int> d;
std::queue<int> q;inline void Floyd() {f.resize(n + 1, std::vector<int>(n + 1, INF));f = e;Rep(i, 1, n + 1) f[i][i] = 0;Rep(k, 1, n + 1) {Rep(i, 1, n + 1) {Rep(j, 1, n + 1) {if(f[i][k] < INF && f[k][j] < INF) {f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);}}}}}
傳遞閉包（Floyd）:
inline void Floyd() {Rep(k, 1, n + 1) {Rep(i, 1, n + 1) {Rep(j, 1, n + 1) {e[i][j] |= (e[i][k] & e[k][j]);}}}}
Floyd（bitset優化）:
#include <iostream>
#include <climits>
#include <limits>
#include <vector>
#include <bitset>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();int n;
std::vector<std::bitset<110>> e;inline void Floyd() {Rep(j, 1, n + 1) Rep(i, 1, n + 1) if(e[i][j]) e[i] |= e[j];
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n;e.resize(n + 1);Rep(i, 1, n + 1) {Rep(j, 1, n + 1) {int val;std::cin >> val;e[i][j] = val;}}Floyd();Rep(i, 1, n + 1) {Rep(j, 1, n + 1) std::cout << e[i][j] << " ";std::cout << '\n';}return 0;
}
Floyd求無向圖最小環：
int MinCycle(int n) {int res = INF;vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));Rep(i, 1, n + 1) d[i][i] = 0;Rep(i, 1, m + 1) {int u, v, w;cin >> u >> v >> w;d[u][v] = d[v][u] = min(d[u][v], w); // 處理重邊}Rep(k, 1, n + 1) {rep(i, k) Rep(j, i + 1, k) res = min(res, d[i][j] + d[i][k] + d[k][j]);Rep(i, 1, n + 1) Rep(j, 1, n + 1) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}return res == INF ? -1 : res; // 無環返回-1
}
差分約束:
#include <iostream>
#include <climits>
#include <limits>
#include <vector>
#include <queue>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();int n, m;
std::vector<std::vector<PII>> e;
std::vector<int> dist, cnt;
std::vector<bool> vis;
std::queue<int> q;inline void SPFA() {q.push(0);dist[0] = 0;vis[0] = true;cnt[0]++;while(!q.empty()) {int u = q.front();q.pop();vis[u] = false;for(const auto&[v, w] : e[u]) {if(dist[v] > dist[u] + w) {dist[v] = dist[u] + w;if(!vis[v]) {q.push(v);vis[v] = true;cnt[v]++;if(cnt[v] > n) {std::cout << "NO\n";exit(0);}}}}}
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> m;dist.resize(n + 1, INF);e.resize(n + 1);vis.resize(n + 1, false);cnt.resize(n + 1, 0);Rep(i, 1, n + 1) e[0].push_back({i, 0});rep(i, m) {int a, b, c;std::cin >> a >> b >> c;e[b].push_back({a, c});}SPFA();Rep(i, 1, n + 1) std::cout << dist[i] << " ";return 0;
}prim:
int N, M, res = 0, cnt = 0;
std::vector<std::vector<int>> e;
std::vector<int> dist;
std::vector<bool> vis;inline void prim() {dist[1] = 0;rep(i, N) {int t = -1;Rep(j, 1, N + 1) if (!vis[j] && (t == -1 || dist[j] < dist[t])) t = j;if (t == -1 || dist[t] == INF) break;vis[t] = true;res += dist[t];cnt++;Rep(j, 1, N + 1) if (!vis[j]) dist[j] = std::min(dist[j], e[t][j]);}
}
Kruskal:
struct edge {ll u, v, w;bool operator< (const edge& other) const{return w < other.w;}
};ll N, K, res = 0;
std::vector<edge> e;
std::vector<ll> dist, fa;
std::unordered_map<ll, bool> mp;ll Findest(ll x) {return x == fa[x] ? x : fa[x] = Findest(fa[x]);
}inline void Kruskal() {std::sort(e.begin(), e.end());Rep(i, 1, N + 1) fa[i] = i;rep(i, e.size()) {ll u = e[i].u, v = e[i].v, w = e[i].w;ll fu = Findest(u), fv = Findest(v);if(fu == fv) continue;res += w;fa[fu] = fv;}}
LCA（倍增）:
#include <iostream>
#include <climits>
#include <limits>
#include <vector>
#include <cmath>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();int N, M, S, LOG;
std::vector<std::vector<int>> e, fa;
std::vector<int> dep;void DFS(int u, int father) {dep[u] = dep[father] + 1;fa[u][0] = father;for(int i = 1; i < LOG; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];for(const int& v : e[u]) if(v != father) DFS(v, u);
}inline int LCA(int u, int v) {if(dep[u] < dep[v]) std::swap(u, v);for(int i = LOG - 1; i >= 0; i--) if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];if(u == v) return v;for(int i = LOG - 1; i >= 0; i--) if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i]; return fa[u][0];
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> N >> M >> S;LOG = log2(N) + 1;e.resize(N + 1);fa.resize(N + 1, std::vector<int>(LOG, 0));dep.resize(N + 1, 0);rep(i, N - 1) {int x, y;std::cin >> x >> y;e[x].push_back(y);e[y].push_back(x); }dep[S] = 0;DFS(S, 0);while(M--) {int x, y;std::cin >> x >> y;std::cout << LCA(x, y) << '\n';}return 0;
}LCA（樹鏈剖分）:
void DFS1(int u, int father) {dep[u] = dep[father] + 1, sz[u] = 1, fa[u] = father;for(const int& v : e[u]) {if(v == father) continue;DFS1(v, u);sz[u] += sz[v];if(sz[son[u]] < sz[v]) son[u] = v; }
}void DFS2(int u, int t) {top[u] = t;if(!son[u]) return ;DFS2(son[u], t);for(const int& v : e[u]) if(v != fa[u] && v != son[u]) DFS2(v, v);
}inline int LCA(int u, int v) {while(top[u] != top[v]) {if(dep[top[u]] < dep[top[v]]) std::swap(u, v);u = fa[top[u]];}return dep[u] < dep[v] ? u : v;
}
Kruskal重構樹：
構建最大生成樹，建立起來的父節點都是兩點之間最小邊權的最大值
構建最小生成樹，建立起來的父節點都是兩點之間最大邊權的最小值
#include <iostream>
#include <climits>
#include <limits>
#include <vector>
#include <algorithm>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();struct edge {int u, v, w;bool operator> (const edge& other) const{return w > other.w;}
};int n, m, q;
std::vector<edge> adj;
std::vector<std::vector<int>> e;
std::vector<int> dist, sz, dep, son, top, fa, F, cost;inline void Init() {std::cin >> n >> m;sz.resize(2 * n + 1, 0);dep.resize(2 * n + 1, 0);fa.resize(2 * n + 1, 0);F.resize(2 * n + 1, 0);son.resize(2 * n + 1, 0);cost.resize(2 * n + 1, -1);top.resize(2 * n + 1, 0);e.resize(2 * n + 1);}void DFS1(int u, int father) {dep[u] = dep[father] + 1, sz[u] = 1, fa[u] = father;for(const int& v : e[u]) {if(v == father) continue;DFS1(v, u);sz[u] += sz[v];if(sz[son[u]] < sz[v]) son[u] = v; }
}void DFS2(int u, int t) {top[u] = t;if(!son[u]) return ;DFS2(son[u], t);for(const int& v : e[u]) if(v != fa[u] && v != son[u]) DFS2(v, v);
}inline int LCA(int u, int v) {while(top[u] != top[v]) {if(dep[top[u]] < dep[top[v]]) std::swap(u, v);u = fa[top[u]];}return dep[u] < dep[v] ? u : v;
}int Findest(int x) {return x == F[x] ? x : F[x] = Findest(F[x]);
}inline void KruskalBuildTree() {std::sort(adj.begin(), adj.end(), std::greater<edge>());Rep(i, 1, n + 1) F[i] = i;int tot = n;rep(i, adj.size()) {int u = adj[i].u, v = adj[i].v, w = adj[i].w;int fu = Findest(u), fv = Findest(v);if(fu == fv) continue;cost[++tot] = w;F[tot] = F[fu] = F[fv] = tot;e[tot].push_back(fu);e[tot].push_back(fv);e[fu].push_back(tot);e[fv].push_back(tot);}Rep(i, 1, tot + 1) if(F[i] == i) DFS1(i, 0), DFS2(i, i);
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);Init();rep(i, m) {int a, b, c;std::cin >> a >> b >> c;adj.push_back({a, b, c});}KruskalBuildTree();std::cin >> q;while(q--) {int x, y;std::cin >> x >> y;std::cout << cost[LCA(x, y)] << '\n';}return 0;
}Tarjan（scc）:
int n, m, tot = 0, cnt = 0;
std::vector<std::vector<int>> e;
std::vector<int> low, dfn, id, sz;
std::vector<bool> in_stk;
std::stack<int> stk;void Tarjan(int u) {low[u] = dfn[u] = ++tot;stk.push(u), in_stk[u] = true;for(const int& v : e[u]) {if(!dfn[v]) {Tarjan(v);low[u] = std::min(low[u], low[v]);}else if(in_stk[v]) low[u] = std::min(low[u], dfn[v]);}if(dfn[u] == low[u]) {int v;cnt++;do{v = stk.top();stk.pop();in_stk[v] = false;id[v] = cnt;sz[cnt]++;}while(v != u);}
}
Tarjan（scc割邊）:
void Tarjan(int u, int father) {low[u] = dfn[u] = ++tot;for(const int& v : e[u]) {if(v == father) continue;if(!dfn[v]) {Tarjan(v, u);low[u] = std::min(low[u], low[v]);if(low[v] > dfn[u]) output.push_back({u, v});}else low[u] = std::min(low[u], dfn[v]);}
}
Tarjan（scc割點）:
inline void Tarjan(int u) {low[u] = dfn[u] = ++cnt;int child = 0;for(const int& v : e[u]) {if(!dfn[v]) {Tarjan(v);low[u] = std::min(low[u], low[v]);if(low[v] >= dfn[u]) {child++;if(child > 1 || u != root) cut[u] = true;}}else low[u] = std::min(low[u], dfn[v]);}
}
Tarjan（edcc）：
int n, m, tot = 0, cnt = 0;
std::vector<edge> e;
std::vector<int> low, dfn, h, bri, dcc, d ;
std::stack<int> stk;inline void add(int a, int b) {e.push_back({b, h[a]});h[a] = e.size() - 1;
}void Tarjan(int u, int in_edge) {low[u] = dfn[u] = ++tot;stk.push(u);for(int i = h[u]; ~i; i = e[i].ne) {int v = e[i].v;if(!dfn[v]) {Tarjan(v, i);low[u] = std::min(low[u], low[v]);if(low[v] > dfn[u]) bri[i] = bri[i ^ 1] = true;}else if(i != (in_edge ^ 1)) low[u] = std::min(low[u], dfn[v]);}if(dfn[u] == low[u]) {int v;cnt++;do{v = stk.top();stk.pop();dcc[v] = cnt;}while(v != u);}
}
Tarjan（vdcc）:
int n, m, tot = 0, cnt = 0;
std::vector<std::vector<int>> e;
std::vector<int> low, dfn, dcc;
std::stack<int> stk;inline void Tarjan(int u) {low[u] = dfn[u] = ++cnt;if(e[u].empty()) {dcc[++cnt].push_back(u);return ;}int child = 0;for(const int& v : e[u]) {if(!dfn[v]) {Tarjan(v);low[u] = std::min(low[u], low[v]);if(low[v] >= dfn[u]) {child++;if(child > 1 || u != root) cut[u] = true;int ne;cnt++;do{ne = stk.top();stk.pop();dcc[cnt].push_back(ne);}while(ne != u);}}else low[u] = std::min(low[u], dfn[v]);}
}main(建圖)：
//給每個割點一個新編號（cnt+1開始）
num = cnt;
Rep(i, 1, n + 1) if(cut[i]) id[i] = ++num;
//建新圖，從每個vDCC向對應割點連邊
Rep(u, 1, cnt + 1){for(const int& v : e[u]){if(cut[v]){ne[i].push_back(id[v]);ne[id[v]].push_back(i);}}
}2-SAT:
int n, m, tot = 0, cnt = 0;
std::vector<std::vector<int>> e;
std::vector<int> low, dfn, id, sz;
std::vector<bool> in_stk;
std::stack<int> stk;void Tarjan(int u) {low[u] = dfn[u] = ++tot;stk.push(u), in_stk[u] = true;for(const int& v : e[u]) {if(!dfn[v]) {Tarjan(v);low[u] = std::min(low[u], low[v]);} else if(in_stk[v]) low[u] = std::min(low[u], dfn[v]);}if(dfn[u] == low[u]) {int v;cnt++;do{v = stk.top();stk.pop();in_stk[v] = false;id[v] = cnt; // 記錄SCC編號sz[cnt]++;}while(v != u);}
}// 添加約束：x取a或y取b（a,b∈{0,1}）
// 注意：變量x的編號應為0到n-1
void add_clause(int x, int a, int y, int b) {// 變量x的真值為2x，假值為2x+1int u = 2 * x + a;int v = 2 * y + b;e[u ^ 1].push_back(v); // ?u → ve[v ^ 1].push_back(u); // ?v → u
}bool solve_2sat() {// 初始化數組dfn.resize(2 * n + 2, 0);low.resize(2 * n + 2, 0);id.resize(2 * n + 2, 0);sz.resize(2 * n + 2, 0);in_stk.resize(2 * n + 2, false);e.resize(2 * n + 2);rep(i, 2 * n) if (!dfn[i]) Tarjan(i);// 檢查每個變量的兩個狀態是否在同一SCC中rep(i, n) if (id[2 * i] == id[2 * i+1]) return false;return true;
}
歐拉回路（有向圖）：
1.對于無向圖
（1）存在歐拉路徑的充分必要條件：度數為奇數的點只能有0或2個。
（2）存在歐拉回路的充分必要條件：度數為奇數的點只能有0個。2.對于有向圖，所有邊都是連通。
（1）存在歐拉路徑的充分必要條件：要么所有點的出度均等于入度；要么除了兩個
點之外，其余所有點的出度等于入度，剩余的兩個點：一個滿足出度比入度多1（起
點），另一個滿足入度比出度多1（終點）。
（2）存在歐拉回路的充分必要條件：所有點的出度均等于入度。#include <iostream>
#include <climits>
#include <limits>
#include <vector>
#include <algorithm>
#include <stack>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();int n, m, s = 1;
std::vector<std::vector<int>> e;
std::vector<int> din, dout, del;
std::stack<int> stk;void DFS(int u) {for(int i = del[u]; i < e[u].size(); i = del[u]) {del[u] = i + 1;DFS(e[u][i]);}stk.push(u);
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> n >> m;e.resize(n + 1);din.resize(n + 1);dout.resize(n + 1);del.resize(n + 1, 0);rep(i, m) {int a, b;std::cin >> a >> b;e[a].push_back(b);din[b]++, dout[a]++;}Rep(i, 1, n + 1) std::sort(e[i].begin(), e[i].end());int cnt_out = 0, cnt_in = 0;bool flag = false;Rep(i, 1, n + 1) {if(din[i] != dout[i]) { // 有入度出度不相等的點 flag = true;int delta = dout[i] - din[i]; // 出度 - 入度if(delta == 1) cnt_out++, s = i; // 起點else if(delta == -1) cnt_in++;else {std::cout << "No\n";return 0;}}}if(flag && cnt_in != cnt_out && cnt_out != 1) {std::cout << "No\n";return 0;}DFS(s);while(!stk.empty()) std::cout << stk.top() << " ", stk.pop();return 0;
}歐拉回路（無向圖）：
#include <iostream>
#include <climits>
#include <limits>
#include <vector>
#include <stack>
#include <unordered_map>
#include <algorithm>typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef std::pair<int, int> PII;#define rep(i, n) for(int i = 0; i < n; i++)
#define Rep(i, len, n) for(int i = len; i < n; i++)
#define MAX_INT 0x7fffffff
#define MIN_INT 0x80000000const int INF = std::numeric_limits<int>::max();int m;
std::vector<std::vector<int>> e;
//std::vector<std::vector<bool>> vis;
std::vector<int> odd, d;
std::unordered_map<int, std::unordered_map<int, int>> mp;
std::stack<int> stk;void DFS(int u) {/*// 如果兩點間只能一條路徑經過一次while(!e[u].empty()) {int v = e[u].back();e[u].pop_back();if(vis[u][v] || vis[v][u]) continue;vis[u][v] = vis[v][u] = true;DFS(v);}*/// 如果兩點有多條路徑，并且每條路徑都能經過一次for(const int& v : e[u]) {if(mp[u][v]) {mp[u][v]--;mp[v][u]--;DFS(v);}}stk.push(u);
}int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);std::cin >> m;e.resize(500 + 1);d.resize(500 + 1);//vis.resize(500 + 1, std::vector<bool>(500 + 1, false));//mp.resize(500 + 1, std::vector<int>(500 + 1, 0));rep(i, m) {int a, b;std::cin >> a >> b;e[a].push_back(b);e[b].push_back(a);mp[a][b]++, mp[b][a]++;d[a]++, d[b]++;}Rep(i, 1, 500 + 1) if(!e[i].empty()) std::sort(e[i].begin(), e[i].end());Rep(i, 1, 500 + 1) if(!e[i].empty() && d[i] & 1) odd.push_back(i); // 不是孤點，并且是奇數int s = INF;if(odd.size() == 2) s = std::min(odd[0], odd[1]);else {Rep(i, 1, 500 + 1) {if(d[i]) {s = i;break;}}}if(s == INF) s = 1;DFS(s);while(!stk.empty()) std::cout << stk.top() << '\n', stk.pop();return 0;
}
樹的直徑：
int max_v = 0;
std::vector<std::vector<PII>> e;
std::vector<int> dist, from, a;void DFS(int u, int fa) {from[u] = fa; // 記錄直徑路徑上的點for(const auto& [v, w] : e[u]) {if(v == fa) continue;dist[v] = dist[u] + w; // 記錄距離if(dist[v] > dist[max_v]) max_v = v; // 更新于起點最遠的點DFS(v, u);}
}inline void Build(int u) {while(u) { // 獲取路徑(反向)a。push_back(u);u = from[u];}std::reverse(a.begin(), a.end()); // 變成從起點到終點
}inline void TreeL() {DFS(1, 0);dist[max_v] = 0;DFS(max_v, 0);Build(max_v);
}
樹的重心：
樹的中心：
樹中所有節點的最長最短路徑的中點（即樹的直徑的中點）
應用場景：選擇一個點，使得最遠節點的距離最小（如緊急集合點問題）。樹的重心：
樹中所有節點到該點的距離之和最小的點
應用場景：選擇一個點，使得所有節點的距離總和最小
int n;
std::vector<std::vector<int>> e;
std::vector<int> sz, dist, d;
std::vector<bool> vis;int DFS(int u){vis[u] = true; //標記u這個點被搜過int sz = 0; //記錄u的最大子樹的結點數int sum = 1; //記錄以u為根的子樹的結點數for(const int& v : e[u]){ if(vis[v]) continue; //避免向上查找int s = DFS(v); //s是以v為根的子樹的結點數sz = std::max(sz,s); //記錄u的最大子樹的結點數sum += s; //累加u的各個子樹的結點數}ans = min(ans, max(sz, n - sum)); //去掉重心每個區間最大的節點數的最小值return sum; //返回以u為根的子樹的結點數
}
樹的中心：
int n, sum = 0;std::vector<std::vector<int>> e;std::vector<int> d1, d2, up, p;std::vector<bool> vis;// 向下找找到最長路徑和次長路徑int DFSDown(int u, int fa) {d1[u] = d2[u] = 0;for(const int& v : e[u]) {if(v == fa) continue;int d = DFSDown(v, u) + 1;if(d >= d1[u]) {d2[u] = d1[u];d1[u] = d;p[u] = v; // 記錄u的子節點是誰}else if(d > d2[u]) d2[u] = d;}return d1[u];}// 向上查找，如果說 v 位于最長路，則比較次長路和向上走那個距離更遠，更新up[v]// 如果說 v 位于次長路，則比較最長路和向上走那個距離更遠，更新up[v]void DFSUp(int u, int fa) {for(const int& v : e[u]) {if(v == fa) continue;if(p[u] == v) up[v] = std::max(up[u], d2[u]) + 1;else up[v] = std::max(up[u], d1[u]) + 1;DFSUp(v, u);}}main(輸出樹的中心)：DFSDown(任意點x, -1);
DFSUp(任意點x, -1);int res = INF;
Rep(i, 1, n + 1) res = std::min(res, std::max(up[i], d1[i]));
std::cout << res << '\n';
樹上操作整合：
const int INF = std::numeric_limits<int>::max();int n, sum = 0, max_v = 0, ans = INF;
std::vector<std::vector<PII>> e;
std::vector<int> sz, dist, d, d1, d2, up, p, from, a;
std::vector<bool> vis;// 樹的直徑
void DFS(int u, int fa) {from[u] = fa; // 記錄直徑路徑上的點for (const auto& [v, w] : e[u]) {if (v == fa) continue;dist[v] = dist[u] + w; // 記錄距離if (dist[v] > dist[max_v]) max_v = v; // 更新于起點最遠的點DFS(v, u);}
}// 樹的重心(重載)
int DFS(int u) {vis[u] = true; // 標記u這個點被搜過sz[u] = 1; // 初始化以u為根的子樹的結點數int max_sz = 0; // 記錄u的最大子樹的結點數for (const auto& [v, w] : e[u]) {if (vis[v]) continue; // 避免向上查找int s = DFS(v); // s是以v為根的子樹的結點數sz[u] += s; // 累加u的各個子樹的結點數max_sz = std::max(max_sz, s); // 記錄u的最大子樹的結點數}ans = std::min(ans, std::max(max_sz, n - sz[u])); // 計算去掉u后最大子樹的節點數return sz[u]; // 返回以u為根的子樹的結點數
}// 向下找找到最長路徑和次長路徑
int DFSDown(int u, int fa) {d1[u] = d2[u] = 0;for (const auto& [v, w] : e[u]) {if (v == fa) continue;int d = DFSDown(v, u) + 1;if (d >= d1[u]) {d2[u] = d1[u];d1[u] = d;p[u] = v; // 記錄u的子節點是誰}else if (d > d2[u]) d2[u] = d;}return d1[u];
}// 向上查找，如果說 v 位于最長路，則比較次長路和向上走那個距離更遠，更新up[v]
// 如果說 v 位于次長路，則比較最長路和向上走那個距離更遠，更新up[v]
void DFSUp(int u, int fa) {for (const auto& [v, w] : e[u]) {if (v == fa) continue;if (p[u] == v) up[v] = std::max(up[u], d2[u]) + 1;else up[v] = std::max(up[u], d1[u]) + 1;DFSUp(v, u);}
}inline void Build(int u) {while (u) { // 獲取路徑(反向)a.push_back(u);u = from[u];}std::reverse(a.begin(), a.end()); // 變成從起點到終點
}inline void TreeL() { // 獲得直徑DFS(1, 0);dist[max_v] = 0;DFS(max_v, 0);Build(max_v);
}inline int TreeMid(int x) { // 獲得中心DFSDown(x, 0);up[1] = 0;DFSUp(x, 0);int res = INF;Rep(i, 1, n + 1) res = std::min(res, std::max(up[i], d1[i]));std::cout << res << '\n';return res;
}inline int Centroid(int x) { // 獲得返回以x為根的子樹的重心std::fill(vis.begin(), vis.end(), false);ans = INF;int s = DFS(x); // 重載的DFS計算重心(s是以x為根的子樹的結點數)// 找到最小的最大子樹節點數對應的節點int centroid = -1;Rep(i, 1, n + 1) {if (!vis[i]) continue; // 只考慮子樹中的節點int max_sub = std::max(sz[i], s - sz[i]); // s是子樹大小if (max_sub == ans) {centroid = i;break;}}return centroid;
}inline void Init(int n) {e.resize(n + 1);sz.resize(n + 1);dist.resize(n + 1);d.resize(n + 1);d1.resize(n + 1);d2.resize(n + 1);up.resize(n + 1);p.resize(n + 1);from.resize(n + 1);vis.resize(n + 1, false);
}
![[已解決] LaTeX “Unicode character“ 報錯 (中文字符處理)](http://pic.xiahunao.cn/[已解決] LaTeX “Unicode character“ 報錯 (中文字符處理))
調度邏輯)
