一道图论相关的题目
3108. 带权图里旅途的最小代价
结论:
做与运算,结果不会大于当前值,也就是说与运算只能导致结果不变或越来越小,所以要使得边的and值最小,就是把每一个联通块的所有边都and一遍。
方法1:dfs
深度优先遍历每一个节点,并计算该节点所在的联通块内所有边的与值
两个点的联通情况,分三种可能:
1、两个点不在同一个联通块
2、两个点在一个联通块
3、两个点相同
class Solution {
// 从u节点出发,计算联通块id里的边and值
// u输入联通块id
public int dfs(int u, int id, List<int[]>[] g, int[] ids) {
ids[u] = id;
int ans = -1; // -1的二进制数所有位全为1, -1 & x = x
for (int[] cur : g[u]) {
int v = cur[0];
int w = cur[1];
ans = ans & w; // 注意这句不能写在下面if里,如果写在if里,则不能保证所有的边都被and (因为两个节点的边可能不止一条),见解释1
if (ids[v] == -1) {
// 从u能走到v,说明v也属于联通块id
ans = ans & dfs(v, id, g, ids);
}
}
return ans;
}
public int[] minimumCost(int n, int[][] edges, int[][] query) {
List<int[]>[] g = new ArrayList[n]; // g[x]:表示从x节点出边的<入点,边>集合
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<>();
}
for (int[] e : edges) {
int u = e[0];
int v = e[1];
int w = e[2];
g[u].add(new int[]{v, w});
g[v].add(new int[]{u, w});
}
int[] ids = new int[n]; // 计算每一个节点(0 ~ n-1)所在的联通块编号
Arrays.fill(ids, -1);
ArrayList<Integer> andAns = new ArrayList<>(); // 每一个联通块的边的and值
for (int i = 0; i < n; ++i) {
// 计算所有点的联通块编号
if (ids[i] == -1) {
// i节点未计算过
andAns.add(dfs(i, andAns.size(), g, ids));
}
}
int[] res = new int[query.length];
int index = 0;
for (int[] q : query) {
int x = q[0];
int y = q[1];
/**
分三种情况:
1. x和y不属于同一个联通快,返回-1
2. x和y属于同一个联通块,返回联通块的and值
3. x和y相同,返回0
*/
if (ids[x] != ids[y]) {
res[index++] = -1;
}
else if (ids[x] == ids[y]) {
res[index++] = andAns.get(ids[x]);
} else if (x == y) {
res[index++] = 0;
}
}
return res;
}
}
解释1:如果把
ans = ans & w;
写在if里,就会忽略1这条边或者2这条边。因为假设and了1这条边,ids[1]
就不为-1了,当遍历2这条边的时候,不会执行if里的语句。
补充:
Arrays.fill(数组名, 填充值);
例如:
int[] ids = new int[n];
Arrays.fill(ids, -1);
方法2:并查集
遍历每一条边,如果边的两个节点不在一个集合,就合并,并计算新集合的and值
class Solution {
public int find(int x, int[] p) {
if (x != p[x]) {
p[x] = find(p[x], p);
}
return p[x];
}
public int[] minimumCost(int n, int[][] edges, int[][] query) {
int[] p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
int[] and = new int[n]; // 代表节点的and值
Arrays.fill(and, -1);
for (int[] e : edges) {
int u = e[0];
int v = e[1];
int w = e[2];
int uFather = find(u, p);
int vFather = find(v, p);
and[vFather] &= w;
if (uFather != vFather) {
// u和v不在同一个集合就合并
// u所在的集合合并到v所在的集合
and[vFather] &= and[uFather]; // 只计算代表节点的and值
p[uFather] = vFather;
}
}
int[] res = new int[query.length];
int index = 0;
for (int[] q : query) {
int u = q[0];
int v = q[1];
res[index++] = u == v ? 0 : find(u, p) == find(v, p) ? and[find(u, p)] : -1;
}
return res;
}
}