2959. 关闭分部的可行集合数目(困难)twice

Posted on In Views:

1，问题描述

2959. 关闭分部的可行集合数目

难度：困难

一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。

公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。

两个分部之间的 距离 是通过道路长度之和的 最小值 。

给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。

请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。

注意，关闭一个分部后，与之相连的所有道路不可通行。

注意，两个分部之间可能会有多条道路。

示例 1：

img

1
2
3
4
5
6
7
8
9
输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
输出：5
解释：可行的关闭分部方案有：
- 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 5 种可行的关闭方案。

示例 2：

img

1
2
3
4
5
6
7
8
9
10
11
输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
输出：7
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。
- 关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。
- 关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 7 种可行的关闭方案。

示例 3：

1
2
3
4
5
6
输入：n = 1, maxDistance = 10, roads = []
输出：2
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0] 。
- 关闭分部集合 [0] ，关闭后没有剩余分部。
总共有 2 种可行的关闭方案

提示：

  • 1 <= n <= 10
  • 1 <= maxDistance <= 105
  • 0 <= roads.length <= 1000
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= wi <= 1000
  • 一开始所有分部之间通过道路互相可以到达。

2，初步思考

​ 使用的是floyd+暴力遍历求解

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _2959关闭分部的可行集合数目 {

    // 动态规划，Floyd最短路径算法
    // 必定可行的方案：0个节点、1个节点
    // 需要简单检测的方案：2个节
    // 需要floyd检测的方案：3个节点以上
    public int numberOfSets(int n, int maxDistance, int[][] roads) {
        res = n + 1;
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }
        for (int[] road : roads) {
            if (road[0] == road[1]) continue;
            int preDis = graph[road[0]][road[1]];
            if (preDis > road[2]) {
                preDis = road[2];
            }
            if (preDis < maxDistance) {// 检测2节点间是否可行
                res++;
            }
            graph[road[0]][road[1]] = preDis;
            graph[road[1]][road[0]] = preDis;
        }
        floyd_check(graph, n, maxDistance, 0, new ArrayList<>());
        return res;
    }

    int res = 0;
    int INF = Integer.MAX_VALUE >> 2;

    private void floyd_check(int[][] graph, int n, int maxDistance, int idx, List<Integer> list) {
        if (list.size() > 2) {// 3个节点以上才需要检测
            boolean resCur = floyd_check_distance(graph, maxDistance, list);
            if (resCur) res++;
        }
        for (int i = idx; i < n; i++) {
            list.add(i);
            floyd_check(graph, n, maxDistance, 0, new ArrayList<>());
            list.removeLast();
        }
    }

    private boolean floyd_check_distance(int[][] graph, int maxDistance, List<Integer> list) {
        int len = list.size();
        int[][] graph_tmp = new int[len][len];
        for (int i = 0; i < len; i++) {
            Arrays.fill(graph_tmp[i], INF);

        }
        return true;
    }

    // 官方题解
    public int numberOfSets_gov(int n, int maxDistance, int[][] roads) {
        int res = 0;
        int[] opened = new int[n];
        int[][] d = new int[n][n];

        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                opened[i] = mask & (1 << i);
            }
            for (int[] row : d) {
                Arrays.fill(row, 1000000);
            }
            for (int[] road : roads) {
                int i = road[0], j = road[1], r = road[2];
                if (opened[i] > 0 && opened[j] > 0) {
                    d[i][j] = d[j][i] = Math.min(d[i][j], r);
                }
            }

            // Floyd-Warshall algorithm
            for (int k = 0; k < n; k++) {
                if (opened[k] > 0) {
                    for (int i = 0; i < n; i++) {
                        if (opened[i] > 0) {
                            for (int j = i + 1; j < n; j++) {
                                if (opened[j] > 0) {
                                    d[i][j] = d[j][i] = Math.min(d[i][j], d[i][k] + d[k][j]);
                                }
                            }
                        }
                    }
                }
            }

            // Validate
            int good = 1;
            for (int i = 0; i < n; i++) {
                if (opened[i] > 0) {
                    for (int j = i + 1; j < n; j++) {
                        if (opened[j] > 0) {
                            if (d[i][j] > maxDistance) {
                                good = 0;
                                break;
                            }
                        }
                    }
                    if (good == 0) {
                        break;
                    }
                }
            }
            res += good;
        }
        return res;
    }


    public static void main(String[] args) {
        _2959关闭分部的可行集合数目 test = new _2959关闭分部的可行集合数目();
        int[][] roads = {{0, 1, 2}, {0, 2, 2}, {1, 2, 1}, {0, 3, 1}, {1, 3, 1}, {2, 3, 1}};
        System.out.println(test.numberOfSets(4, 2, roads));
    }

}