组合数学与图论进阶

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;

// ======================================================
//              第一部分：组合数学
// ======================================================

// ========== 1. 排列 A(n,k) = n! / (n-k)! ==========
ll permutation(int n, int k) {
    ll result = 1;
    for (int i = 0; i < k; i++) result *= (n - i);
    return result;
}

// ========== 2. 组合 C(n,k) = n! / (k!(n-k)!) ==========
// 杨辉三角递推
ll C[1010][1010];
void init_combinations(int n) {
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}

// ========== 3. 杨辉三角 ==========
void print_pascal(int n) {
    init_combinations(n);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << C[i][j] << " ";
        }
        cout << endl;
    }
}

// ======================================================
//              第二部分：并查集
// ======================================================

int fa[N];

void uf_init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i;
}

int uf_find(int x) {
    if (fa[x] != x) fa[x] = uf_find(fa[x]);  // 路径压缩
    return fa[x];
}

void uf_union(int a, int b) {
    fa[uf_find(a)] = uf_find(b);
}

bool uf_connected(int a, int b) {
    return uf_find(a) == uf_find(b);
}

// ======================================================
//              第三部分：最小生成树
// ======================================================

// ========== 4. Kruskal 算法 ==========
struct Edge {
    int u, v, w;
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

ll kruskal(int n, vector<Edge> &edges) {
    sort(edges.begin(), edges.end());
    uf_init(n);

    ll totalWeight = 0;
    int edgeCount = 0;

    for (auto &e : edges) {
        if (!uf_connected(e.u, e.v)) {
            uf_union(e.u, e.v);
            totalWeight += e.w;
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }

    if (edgeCount < n - 1) return -1;  // 图不连通
    return totalWeight;
}

// ========== 5. Prim 算法 ==========
ll prim(int n, vector<vector<pii>> &adj) {  // adj[u] = {v, w}
    vector<int> dist(n + 1, INF);
    vector<bool> inMST(n + 1, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    ll totalWeight = 0;
    int nodeCount = 0;

    while (!pq.empty() && nodeCount < n) {
        auto [d, u] = pq.top();
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += d;
        nodeCount++;

        for (auto [v, w] : adj[u]) {
            if (!inMST[v] && w < dist[v]) {
                dist[v] = w;
                pq.push({w, v});
            }
        }
    }

    return totalWeight;
}

// ======================================================
//              第四部分：最短路
// ======================================================

// ========== 6. Dijkstra 算法（单源最短路）==========
// 适用于非负权图
ll dist_dijk[N];

void dijkstra(int start, int n, vector<vector<pii>> &adj) {
    fill(dist_dijk, dist_dijk + n + 1, INF);
    dist_dijk[start] = 0;

    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist_dijk[u]) continue;  // 已有更短路径

        for (auto [v, w] : adj[u]) {
            if (dist_dijk[u] + w < dist_dijk[v]) {
                dist_dijk[v] = dist_dijk[u] + w;
                pq.push({dist_dijk[v], v});
            }
        }
    }
}

// ========== 7. Floyd 算法（多源最短路）==========
int floyd_dist[510][510];

void floyd(int n) {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                floyd_dist[i][j] = min(floyd_dist[i][j],
                    floyd_dist[i][k] + floyd_dist[k][j]);
}

// ======================================================
//              第五部分：倍增法
// ======================================================

// ========== 8. 倍增法求 RMQ（区间最小值）==========
int st[N][20];  // st[i][j]: 从 i 开始 2^j 个元素的最小值
int log2_table[N];

void sparse_table_init(int a[], int n) {
    log2_table[1] = 0;
    for (int i = 2; i <= n; i++) log2_table[i] = log2_table[i/2] + 1;

    for (int i = 0; i < n; i++) st[i][0] = a[i];

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
}

int range_min(int l, int r) {
    int k = log2_table[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 组合数学
    init_combinations(100);
    cout << "C(10,3) = " << C[10][3] << endl;  // 120

    // Dijkstra
    int n, m, start;
    cin >> n >> m >> start;
    vector<vector<pii>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});  // 无向图
    }
    dijkstra(start, n, adj);
    for (int i = 1; i <= n; i++) {
        cout << i << ": " << dist_dijk[i] << endl;
    }

    return 0;
}

📖 要点说明

组合数学核心公式

两种最小生成树对比

两种最短路对比

倍增法

• 预处理 2^k 倍信息，查询 O(log n)
• 典型应用：RMQ、LCA（最近公共祖先）

⚠️ 常见错误

• Dijkstra 不能处理负权边，有负权用 Bellman-Ford 或 SPFA
• Floyd 初始化：对角线 = 0，没边的 = INF，注意 INF 不能太大避免溢出
• Kruskal 中并查集要先初始化
• 倍增法 log2_table 要预计算，不要每次调库函数