做常识的网站,中国核工业二三建设有限公司招聘,竞价网官网,桂林网站开发公司文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;2959. 关闭分部的可行集合数目
2. 题目解析
看了看题好像还没啥思路#xff0c;结果一看数据范围#xff0c;好家伙…n 最大就 10 啊#xff0c;那不直接闭眼直接 Floyd枚举所有情况即可吗#xff1f;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, vectorvectorint roads) {int r roads.size();// 2进制枚举int res 0;vectorbool 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;}
};
