题解 | #小红的转账设置方式#

D. 小红的转账设置方式

这题分两部

• 最短路计算

• 计算总方案数

求最小总代价，这个BFS最短路就可以出来

难点在于: 总方案数

这个方案总数和边的方向有关

在保证最小代价不变的情况下，也就是保证每个点的最小路径不变(有向图）

可以观察到

1. 图存在两种类型的边

• 参与最短路的边
• 没有参与最短路的边

2. 如何处理参与最短路的边

参与最短路的边，实际上 仅 属于一个集合，由集合贡献

3. 如何处理非参与最短路的边

这类边，正反都可以，不影响结果，贡献2

分析到这里，这题的解题思路就很容易了。

• 先BFS预处理所有的点(最短路）
• 从点出发，找到上游的点集(边集), 贡献
• 找到剩下的非参与最短路的点集, 贡献2
• 乘法原理

import java.io.*;
import java.util.*;

public class Main {

    static long ksm(long b, long v, long mod) {
        long r = 1l;
        while (v > 0) {
            if (v % 2 == 1) {
                r = r * b % mod;
            }
            b = b * b % mod;
            v /= 2;
        }
        return r;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int n = sc.nextInt(), m = sc.nextInt();

        List<Integer>[]g = new List[n + 1];
        Arrays.setAll(g, x -> new ArrayList<>());

        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            g[u].add(v);
            g[v].add(u);

            edges[i][0] = u;
            edges[i][1] = v;
        }

        long inf = Long.MAX_VALUE / 10;
        long[] cost = new long[n + 1];
        Arrays.fill(cost, inf);

        // BFS求最短路
        Deque<Integer> deq = new ArrayDeque<>();
        deq.offer(1);
        cost[0] = cost[1] = 0;
        while (!deq.isEmpty()) {
            int cur = deq.poll();
            for (int v : g[cur]) {
                if (cost[v] > cost[cur] + 1) {
                    cost[v] = cost[cur] + 1;
                    deq.offer(v);
                }
            }
        }

        // 乘法原理阶段
        long mod = 10_0000_0007l;
        long res = 1l;
        int edgeOfShort = 0; // 参与最短路的边
        // 从2开始计算，忽略节点2
        for (int i = 2; i <= n; i++) {
            int cnt = 0;
            for (int v: g[i]) {
                // 保证上流节点
                if (cost[i] == cost[v] + 1) {
                    cnt++;
                }
            }
            edgeOfShort += cnt;

            // 2^z - 1
            long r = ksm(2l, cnt, mod);
            r = ((r - 1) % mod + mod) % mod;

            // 乘法原理
            res = res * r % mod;
        }

        int edgeOfNone = m - edgeOfShort; // 不参与最短路的边数
        res = res * ksm(2l, edgeOfNone, mod) % mod;

        long minCost = Arrays.stream(cost).sum() % mod;
        System.out.println(minCost + " " + res);

    }

}