6 图论

6.1 迪杰斯特拉 Dijkstra

using pii = pair<int, int>;
using graph = vector<vector<pii>>;
constexpr int INF = 1e18;

vector<int> dijkstra(graph &g, int s) {
    vector<int> dist(g.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (dist[u] < d) continue;
        for (auto [w, v] : g[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

6.2 判断负环 SPFA

用于判断负环是否存在，有负环 return true，否则 return false

bool SPFA(int start, graph &g) {
    int n = (int)g.size();
    vector<int> dist(n, INT_MAX), in_cnt(n, 0);
    bitset<MAXN> vis; // vector<bool> vis(n);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    vis[start] = true;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        vis[now] = false;
        for (auto &[dis, to] : g[now]) {
            if (dist[now] + dis < dist[to]) {
                dist[to] = dist[now] + dis;
                if (!vis[to]) {
                    q.push(to);
                    in_cnt[to]++;
                    if (in_cnt[to] >= (int)g.size()) {
                        return true;
                    }
                    vis[to] = true;
                }
            }
        }
    }
    return false;
}

6.3 拓扑排序 TopoSort

输入图，入度，节点数，返回拓扑序

using vvi = vector<vector<int>>;
vector<int> topoSort(vvi &g, vector<int> indeg) {
    queue<int> q;
    for (size_t i = 0; i < indeg.size(); ++i) {
        if (indeg[i] == 0) q.push(i);
    }
    vector<int> res;
    res.reserve(g.size());
    while (!q.empty()) {
        int u = q.front();
        res.emplace_back(u);
        q.pop();
        for (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    assert(res.size() == g.size());
    return res;
}

6.4 强连通分量

缩点后，从tot到1就是拓扑序，无需再进行拓扑排序。

// Luogu P3387
#include <bits/stdc++.h>
#define int long long
using namespace std;
using vvi = vector<vector<int>>;
constexpr int N = 1e4 + 5;
constexpr int M = 1e5 + 5;
int dfn[N], low[N], tim;
int stk[N], instk[N], tp;
void stkPush(int x) { stk[++tp] = x; instk[x] = 1; }
int stkPop() { int y = stk[tp--]; instk[y] = 0; return y; }
int id[N], tot;
void tarjan(int x, const vvi &g) {
    dfn[x] = low[x] = ++tim;
    stkPush(x);
    for (int y : g[x]) {
        if (!dfn[y]) tarjan(y, g), low[x] = min(low[x], low[y]);
        else if (instk[y]) low[x] = min(low[x], dfn[y]);
    }
    if (low[x] == dfn[x]) {
        tot++;
        while (stk[tp + 1] != x) id[stkPop()] = tot;
    }
}
int n, m, a[N], b[N], f[N], ans;  // b 为新图的点权，f为x新图中到点x的路径点权最大和
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    vvi g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, g);
    vvi h(tot + 1);
    for (int i = 1; i <= n; i++) {
        for (int j : g[i]) { // 缩点
            int x = id[i], y = id[j];
            if (x != y) h[x].emplace_back(y);
        }
    }
    for (int i = 1; i <= n; i++) b[id[i]] += a[i];
    for (int i = 1; i <= tot; i++) { // DAG dp
        f[i] = b[i];
        for (int j : h[i]) f[i] = max(f[i], b[i] + f[j]);
        ans = max(ans, f[i]);
    }
    cout << ans << "\n";
}

6.5 点双连通分量+割点

// Luogu P8435
#include <bits/stdc++.h>
#define int long long
using namespace std;
using vvi = vector<vector<int>>;
constexpr int N = 5e5 + 5;
constexpr int M = 2e6 + 5;
int dfn[N], low[N], tim;
int stk[N], tp;
vvi dcc(N);
int n, m, tot;
bool cut[N];
void tarjan(int x, int fa, const vvi &g) {
    dfn[x] = low[x] = ++tim;
    stk[++tp] = x;
    int child = 0; 
    for (int y : g[x]) {
        if (!dfn[y]) {
            tarjan(y, x, g), low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                child++, tot++;
                if (fa != 0 or child > 1) cut[x] = true;
                while (stk[tp+1] != y) dcc[tot].emplace_back(stk[tp--]);
                dcc[tot].emplace_back(x);
            }
        } else if (y != fa)
            low[x] = min(low[x], dfn[y]);
    }
    if (fa == 0 and child == 0) dcc[++tot].emplace_back(x);  
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    vvi g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0, g);
    cout << tot << "\n";
    for (int i = 1; i <= tot; i++) {
        cout << dcc[i].size();
        for (int j : dcc[i]) cout << " " << j;
        cout << "\n";
    }
}

6.6 边双连通分量+割边

// Luogu P8436
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 5e5 + 5;
constexpr int M = 2e6 + 5;
struct Edge {
    int to, nex;
} e[M * 2];
int head[N], cnt = 1;
void add_edge(int x, int y) {
    e[++cnt] = {y, head[x]};
    head[x] = cnt;
}
int dfn[N], low[N], tim;
int stk[N], tp;
int id[N], tot, bri[M * 2];
void tarjan(int x, int eid) {
    dfn[x] = low[x] = ++tim;
    stk[++tp] = x;
    for (int i = head[x]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!dfn[y]) {
            tarjan(y, i), low[x] = min(low[x], low[y]);
            bri[i] = bri[i ^ 1] = (low[y] > dfn[x]);
        } else if (i != (eid ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
    if (low[x] == dfn[x]) {
        ++tot;
        while (stk[tp + 1] != x) id[stk[tp--]] = tot;
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v), add_edge(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);
    cout << tot << "\n";
    vector<vector<int>> dcc(tot + 1);
    for (int i = 1; i <= n; i++) 
        dcc[id[i]].emplace_back(i);
    for (int i = 1; i <= tot; i++) {
        cout << dcc[i].size();
        for (int j : dcc[i]) cout << " " << j;
        cout << "\n";
    }
}

6.7 最大流

Dinic多路增广。初始正向边c，反向边0。

constexpr int N = 1000005;
constexpr int M = 1000005;
constexpr int INF = 1e18;
int n, m, S, T, ans, tot; // tot 为总的结点个数
struct Edge {int to, c, nex;} e[M*2];
int head[N], cnt = 1;
void add(int u, int v, int c) {
    e[++cnt] = {v, c, head[u]};
    head[u] = cnt;
}
void add_edge(int u, int v, int c) {
    add(u, v, c); add(v, u, 0);
}
int dep[N];
bool bfs() { // 分层
    fill(dep, dep+1+tot, 0);
    queue<int> q;
    q.push(S); dep[S] = 1; 
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nex) {
            int v = e[i].to;
            if (!dep[v] and e[i].c) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[T] != 0;
}
int cur[N];
int dfs(int u, int fin) { // 多路增广
    if (u == T) return fin;
    int fout = 0;
    for (int &i = cur[u]; i and fin; i = e[i].nex) {
        int v = e[i].to;
        if (dep[v] > dep[u] and e[i].c) {
            int f = dfs(v, min(fin, e[i].c));
            fin -= f, fout += f;
            e[i].c -= f, e[i^1].c += f;
        }
    }
    if (fout == 0) dep[u] = 0;
    return fout;
}
int dinic() {
    int flow = 0;
    while (bfs()) {
        copy(head, head+1+tot, cur);
        flow += dfs(S, INF);
    }
    return flow;
}

6.8 费用流

最小费用最大流，SPFA+Dinic。

constexpr int N = 5e3 + 5;
constexpr int M = 5e4 + 5;
constexpr int INF = 1e9;
int n, m, S, T;
struct Edge {
    int to, cap, cost, nex;
} e[M*2];
int head[N], cnt = 1, tot;
void add_edge(int u, int v, int cap, int cost) {
    e[++cnt] = {v, cap, cost, head[u]};
    head[u] = cnt;
}
int dist[N], in[N];
bool spfa() {
    fill(dist, dist+1+tot, INF);
    fill(in, in+1+tot, 0);
    queue<int> q;
    q.emplace(S); dist[S] = 0; in[S] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); in[u] = 0;
        for (int i = head[u]; i; i = e[i].nex) {
            int v = e[i].to;
            if (dist[u] + e[i].cost < dist[v] and e[i].cap) {
                dist[v] = dist[u] + e[i].cost;
                if (!in[v]) q.push(v), in[v] = 1;
            }
        }
    }
    return dist[T] != INF;
}
int cur[N];
int dfs(int u, int fin) {
    if (u == T) return fin;
    int fout = 0;
    in[u] = 1;
    for (int &i = cur[u]; i and fin; i = e[i].nex) {
        int v = e[i].to;
        if (!in[v] and dist[v] == dist[u] + e[i].cost and e[i].cap) {
            int f = dfs(v, min(fin, e[i].cap));
            fin -= f, fout += f;
            e[i].cap -= f, e[i^1].cap += f;
        }
    }
    in[u] = 0;
    if (fout == 0) dist[u] = 0;
    return fout;
}
pair<int, int> dinic() {
    int flow = 0, cost = 0;
    while (spfa()) {
        copy(head, head+1+tot, cur);
        int f = dfs(S, INF);
        flow += f, cost += f * dist[T];
    }
    return {flow, cost};
}