文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:2959. 关闭分部的可行集合数目
2. 题目解析
看了看题好像还没啥思路,结果一看数据范围,好家伙…n 最大就 10 啊,那不直接闭眼直接 Floyd+枚举所有情况即可吗???
果然算法评级只有 6…只需要熟练掌握数据结构即可。
坑点:
- 最终要保持连通,需要特殊判断一下 在这里 WA 一次
- 无向图建双向边
- 时间复杂度: O ( 2 n ∗ n 3 ) O(2^n*n^3) O(2n∗n3)
- 空间复杂度: O ( n 2 ) O(n^2) O(n2)
class Solution {
public:int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {int r = roads.size();// 2进制枚举int res = 0;vector<bool> del(n);for (int i = 0; i < 1 << n; i ++ ) {for (int j = 0; j < n; j ++ ) del[j] = false;for (int j = 0; j < n; j ++ ) if ((i >> j) & 1) del[j] = true;// floyd 建图int d[n][n]; memset(d, 0x3f, sizeof d);for (int j = 0; j < n; j ++ ) d[j][j] = 0;for (int j = 0; j < roads.size(); j ++ ) {int x = roads[j][0], y = roads[j][1], w = roads[j][2];if (del[x] || del[y]) continue;d[x][y] = min(d[x][y], w);d[y][x] = min(d[y][x], w);}// 最短路计算for (int j = 0; j < n; j ++ )for (int k = 0; k < n; k ++ )for (int m = 0; m < n; m ++ )d[k][m] = min(d[k][m], d[k][j] + d[j][m]);// 校验int check = 1;for (int j = 0; j < n; j ++ ) {for (int k = 0; k < n; k ++ ) {if (del[j] || del[k]) continue;if (d[j][k] == 0x3f3f3f3f || d[j][k] > maxDistance) check = 0;}}res += check;}return res;}
};