Author: lllyouo
Date: 20250225
tag: 最小生成树、最短路径生成树
link: https://www.acwing.com/problem/content/351/

问题描述

link

分析

本题旨在求解最短路径生成树的数量。

首先，我们可以使用 Dijkstra 算法求出 $1$ 号房间到每个房间的单源最短路。把树形城堡看作以 $1$ 为根的树，根据题目要求，若 $x$ 是 $y$ 的父节点，且 $x$ 到 $y$ 的距离为 $z$，则有 $dist[y]=dist[x]+z$。如果树中任意一对父子节点都满足上式，则该树称为图的一颗最短路径生成树。

仿照 Prim 算法思路，将所有节点按照 dist 从小到大排序，依次考虑把节点 $p$ 加入生成树中有多少种方法，即考虑有多少个节点 $q$，$q$ 属于生成树的顶点集合且满足 $dist[p]=dist[q]+g[q][p]$，其中 $g[q][p]$ 表示 $q$ 到 $p$ 的边权，此时让 $p$ 与其中任意一个 $q$ 相连，都符合题目要求。

根据乘法原理，把每一步种统计出来的数量相乘，即可得到答案。

参考代码

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

const int N = 1010, MOD = (1 << 31) - 1;
int n, m, g[N][N];
int dist[N], st[N], ans = 1;

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 1; i < n; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (k == -1 || dist[j] < dist[k])) k = j;
        }
        st[k] = 1;

        for (int j = 1; j <= n; j++) {
            if(!st[j] && g[k][j] != 0x3f3f3f3f)
                dist[j] = min(dist[j], dist[k] + g[k][j]);
        }
    }
}

void prime() {
    memset(st, 0, sizeof st);
    st[1] = true;

    for (int i = 1; i < n; i++) {
        int k = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (k == -1 || dist[k] > dist[j]))
                k = j;
        }

        long long cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (st[j] && dist[k] == dist[j] + g[j][k])
                cnt++;
        }

        st[k] = 1;
        ans = (long long)ans * cnt % MOD;
    }
}

int main() {
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    dijkstra();
    prime();

    cout << ans << endl;

    return 0;
}