图对象的定义
package class16; |
边对象的定义
package class16; |
节点对象的定义
package class16; |
BFS
package class16; |
- 主要是在添加一个节点的所有相邻节点到队列里的时候使用了一个set结构判断这个节点是否被添加过，防止无限循环的产生
DFS
package class16;
import java.util.HashSet;
import java.util.Stack;
public class Code02_DFS {
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
HashSet<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
System.out.println(node.value);
while (!stack.isEmpty()) {
Node cur = stack.pop();
for (Node next : cur.nexts) {
if (!set.contains(next)) {
stack.push(cur);
stack.push(next);
set.add(next);
System.out.println(next.value);
break;
}
}
}
}
} - 使用一个栈的数据结构，每从栈中弹出一个节点的时候，遍历该节点的所有邻接点，如果不在已经遍历过的节点的set内，那么先将节点自身进栈，然后再将该邻接节点进栈
最小生成树
- 对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（树中所有边上的权值和）也不同，设R为G的所有生成树的集合，若T为R中权值和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）
kruskal算法
- 并查集：具有检查数据结构中的一些节点是否在同一个集合中、以及将不同的集合合并为一个集合的功能的数据结构
package class16;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;
//undirected graph only
public class Code04_Kruskal {
// Union-Find Set
public static class UnionFind {
// key 某一个节点， value key节点往上的节点
private HashMap<Node, Node> fatherMap;
// key 某一个集合的代表节点, value key所在集合的节点个数
private HashMap<Node, Integer> sizeMap;
public UnionFind() {
fatherMap = new HashMap<Node, Node>();
sizeMap = new HashMap<Node, Integer>();
}
public void makeSets(Collection<Node> nodes) {
fatherMap.clear();
sizeMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
sizeMap.put(node, 1);
}
}
private Node findFather(Node n) {
Stack<Node> path = new Stack<>();
while(n != fatherMap.get(n)) {
path.add(n);
n = fatherMap.get(n);
}
while(!path.isEmpty()) {
fatherMap.put(path.pop(), n);
}
return n;
}
public boolean isSameSet(Node a, Node b) {
return findFather(a) == findFather(b);
}
public void union(Node a, Node b) {
if (a == null || b == null) {
return;
}
Node aDai = findFather(a);
Node bDai = findFather(b);
if (aDai != bDai) {
int aSetSize = sizeMap.get(aDai);
int bSetSize = sizeMap.get(bDai);
if (aSetSize <= bSetSize) {
fatherMap.put(aDai, bDai);
sizeMap.put(bDai, aSetSize + bSetSize);
sizeMap.remove(aDai);
} else {
fatherMap.put(bDai, aDai);
sizeMap.put(aDai, aSetSize + bSetSize);
sizeMap.remove(bDai);
}
}
}
}
public static class EdgeComparator implements Comparator<Edge> {
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
public static Set<Edge> kruskalMST(Graph graph) {
UnionFind unionFind = new UnionFind();
unionFind.makeSets(graph.nodes.values());
// 从小的边到大的边，依次弹出，小根堆！
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
for (Edge edge : graph.edges) { // M 条边
priorityQueue.add(edge); // O(logM)
}
Set<Edge> result = new HashSet<>();
while (!priorityQueue.isEmpty()) { // M 条边
Edge edge = priorityQueue.poll(); // O(logM)
if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
result.add(edge);
unionFind.union(edge.from, edge.to);
}
}
return result;
}
} - findfFather函数是当一个节点具有多级的父亲的时候找到最高级别的父亲，并且修改一路上所有节点的父亲为最高级的父亲
- 算法的思路是先按照权值将图中所有的边都放入小根堆中，将图中所有节点放入并查集中独立存在，然后从堆中依次弹出边，假如边链接的两端不是同一个集合，那么将边放入结果中，同时在并查集中合并两个集合，直到无可合并为止。
prim算法
package class16;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
// undirected graph only
public class Code05_Prim {
public static class EdgeComparator implements Comparator<Edge> {
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
public static Set<Edge> primMST(Graph graph) {
// 解锁的边进入小根堆
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
// 哪些点被解锁出来了
HashSet<Node> nodeSet = new HashSet<>();
Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里
for (Node node : graph.nodes.values()) { // 随便挑了一个点
// node 是开始点
if (!nodeSet.contains(node)) {
nodeSet.add(node);
for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
priorityQueue.add(edge);
}
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll(); // 弹出解锁的边中，最小的边
Node toNode = edge.to; // 可能的一个新的点
if (!nodeSet.contains(toNode)) { // 不含有的时候，就是新的点
nodeSet.add(toNode);
result.add(edge);
for (Edge nextEdge : toNode.edges) {
priorityQueue.add(nextEdge);
}
}
}
}
// break;
}
return result;
}
// 请保证graph是连通图
// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
// 返回值是最小连通图的路径之和
public static int prim(int[][] graph) {
int size = graph.length;
int[] distances = new int[size];
boolean[] visit = new boolean[size];
visit[0] = true;
for (int i = 0; i < size; i++) {
distances[i] = graph[0][i];
}
int sum = 0;
for (int i = 1; i < size; i++) {
int minPath = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < size; j++) {
if (!visit[j] && distances[j] < minPath) {
minPath = distances[j];
minIndex = j;
}
}
if (minIndex == -1) {
return sum;
}
visit[minIndex] = true;
sum += minPath;
for (int j = 0; j < size; j++) {
if (!visit[j] && distances[j] > graph[minIndex][j]) {
distances[j] = graph[minIndex][j];
}
}
}
return sum;
}
public static void main(String[] args) {
System.out.println("hello world!");
}
} - prim算法主要用到一个存储边用的小根堆和一个记录哪些点被解锁的set
- 首先在graph中随便选择一个点，将这个点加入记录解锁的点的集合，然后将这个点的所有边放入优先级队列中，然后开始while循环，每次从优先级队列中弹出一个权值最小的边，假如这个边指向的节点不在前面的set中的话就将这个边指向的节点放入点set中，将这条边放入结果中，然后将该节点延伸出的所有边放入优先级队列中。
Dijkstra算法
- 该算法主要是找到指定起始点到图上剩余所有点的最近距离
package class16;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
// no negative weight
public class Code06_Dijkstra {
public static HashMap<Node, Integer> dijkstra1(Node from) {
HashMap<Node, Integer> distanceMap = new HashMap<>();
distanceMap.put(from, 0);
// 打过对号的点
HashSet<Node> selectedNodes = new HashSet<>();
Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
while (minNode != null) {
// 原始点 -> minNode(跳转点) 最小距离distance
int distance = distanceMap.get(minNode);
for (Edge edge : minNode.edges) {
Node toNode = edge.to;
if (!distanceMap.containsKey(toNode)) {
distanceMap.put(toNode, distance + edge.weight);
} else { // toNode
distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
}
}
selectedNodes.add(minNode);
minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
}
return distanceMap;
}
public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
Node minNode = null;
int minDistance = Integer.MAX_VALUE;
for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
Node node = entry.getKey();
int distance = entry.getValue();
if (!touchedNodes.contains(node) && distance < minDistance) {
minNode = node;
minDistance = distance;
}
}
return minNode;
}
public static class NodeRecord {
public Node node;
public int distance;
public NodeRecord(Node node, int distance) {
this.node = node;
this.distance = distance;
}
} - 算法主要依赖一个记录到对应节点最近距离的哈希表和一个记录某个节点是否已经被锁定的set
- 在初始时刻将起始点到起始点放入哈希表，并且将其距离设置为0。
- 然后的while循环每次都对找出的当前尚未被锁定而且在哈希表中到起始位置距离最小的点指向的所有尚未被锁定的节点的距离进行重算，假如被指向的节点之前的距离小于从该点出发到被指向的点的距离，将被指向点的距离更新为被选中的点出发的距离。（假如被指向的点不存在于哈希表中的话认为被指向的点的距离为正无穷，同样添加该点的距离条目进行更新）。然后将当前选中的点锁定，也就是加入被锁定的点的set中，然后找到当前未被锁定而且从总出发点开始距离最短的点，再次重复循环。
卡码网 29. 安排超市（第一期模拟笔试）
- 此题先用bfs找到每个分立的区域，假如某个独立的区域里具有住户，则需要设置超市，超市尽可能的少
- 然后寻找到每个住户综合距离最小的超市，实际上可以从每个住户出发bfs遍历所在的区域，bfs每前进一层，意味着从住户出发到这个位置的距离+1，由此可以得出住户出发到这个区域每个位置的距离
- 对每个住户执行上述操作然后累加，就可以找出从每个位置出发到每个住户距离之和
- 找出每个区域中距离之和最小的位置即可作为超市的位置
- 注意bfs的时候需要一遇到某个点就在
visited数组中标记这个位置，而不是从队列中弹出的时候再标记这个位置，否则会导致这个位置入队多次，使得算法超时
using namespace std;
// set<pair<int, int>> houses;
// vector<vector<pair<short, short>>> regions;
vector<vector<bool>> visited;
vector<vector<short>> m;
vector<vector<int>> dist;
vector<vector<short>> region;
// vector<vector<bool>> visitedDis;
void bfs4Reg(int x0, int y0, int n, int reg)
{
queue<pair<int, int>> q;
q.push({x0, y0});
region[x0][y0] = reg;
visited[x0][y0] = true;
while(q.size())
{
auto tmp = q.front();
q.pop();
int x = tmp.first;
int y = tmp.second;
// if(m[x][y] == 1)houses.insert({x, y});
if(x>0 && !visited[x-1][y] && m[x-1][y]<2)
{
region[x-1][y] = reg;
visited[x-1][y] = true;
q.push({x-1, y});
}
if(y>0 && !visited[x][y-1] && m[x][y-1]<2)
{
region[x][y-1] = reg;
visited[x][y-1] = true;
q.push({x, y-1});
}
if(x<n-1 && !visited[x+1][y] && m[x+1][y]<2)
{
region[x+1][y] = reg;
visited[x+1][y] = true;
q.push({x+1, y});
}
if(y<n-1 && !visited[x][y+1] && m[x][y+1]<2)
{
region[x][y+1] = reg;
visited[x][y+1] = true;
q.push({x, y+1});
}
}
}
void disFromHouse(int x, int y, int n)
{
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = true;
int curDis = 0;
while (q.size())
{
int v = q.size();
for(int i = 0; i<v; ++i)
{
auto tmp = q.front();
q.pop();
int x = tmp.first;
int y = tmp.second;
dist[x][y] += curDis;
if(x>0 && !visited[x-1][y] && m[x-1][y]<2)
{
q.push({x-1, y});
visited[x-1][y] = true;
}
if(y>0 && !visited[x][y-1] && m[x][y-1]<2)
{
q.push({x, y-1});
visited[x][y-1] = true;
}
if(x<n-1 && !visited[x+1][y] && m[x+1][y]<2)
{
q.push({x+1, y});
visited[x+1][y] = true;
}
if(y<n-1 && !visited[x][y+1] && m[x][y+1]<2)
{
q.push({x, y+1});
visited[x][y+1] = true;
}
}
++curDis;
}
}
int main()
{
int n;
cin>>n;
visited = vector<vector<bool>>(n, vector<bool>(n, false));
m = vector<vector<short>>(n, vector<short>(n, 0));
dist = vector<vector<int>>(n, vector<int>(n, 0));
region = vector<vector<short>>(n, vector<short>(n, 0));
// visitedDis = vector<vector<bool>>(n, vector<bool>(n, false));
char tmp;
for(auto &row:m)
{
for(auto& i:row)
{
cin>>tmp;
switch (tmp)
{
case '*': i = 2;
/* code */
break;
case '.': i = 0;
break;
case '#': i = 1;
break;
default:
break;
}
}
}
if(n == 0)
{
cout<<0<<' '<<0<<endl;
return 0;
}
int regCnt = 0;
for(int i = 0; i<n; ++i)
{
for(int j = 0; j<n; ++j)
{
if(!visited[i][j] && m[i][j]<2)
{
bfs4Reg(i, j, n, regCnt++);
}
}
}
int sumOfDist = 0;
int minDist = INT_MAX;
vector<bool> hasHouse(regCnt, false);
for(int i = 0; i<n; ++i)
{
for(int j = 0; j<n; ++j)
{
if(m[i][j] == 1)
{
visited = vector<vector<bool>>(n, vector<bool>(n, false));
disFromHouse(i, j, n);
hasHouse[region[i][j]] = true;
}
}
}
vector<int> regMin(regCnt, INT_MAX);
for(int i = 0; i<n; ++i)
{
for(int j = 0; j<n; ++j)
{
if(m[i][j]>1)continue;
regMin[region[i][j]] = min(regMin[region[i][j]], dist[i][j]);
}
}
int disSUm = 0;
int marketCnt = 0;
for(int i = 0; i<regCnt; ++i)
{
if(hasHouse[i])
{
disSUm+=regMin[i];
++marketCnt;
}
}
cout<<marketCnt<<' '<< disSUm <<endl;
// cout<<regions.size()<<' '<<0<<endl;
}
牛客美团2024秋招第一场第三题
- 小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。
- 小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。
- 小美想知道，自己最多可以染红多少个节点？
- 此题的关键是防止重复经过同一个节点，因此需要一个
used数组，经过的时候设置为true，经过之后设置为false - 此外就是回溯法寻找，注意一个节点有
标红当前节点和不标红当前节点两种情况
using namespace std;
vector<int>* to;
int* arr;
int* dp;
int* dpf;
bool* red;
int n;
bool* used;
bool isSq(int n)
{
int x = sqrt(n);
if (x*x != n) return false;
return true;
}
int traversal(int beg, bool able)
{
if(used[beg])return 0;
if(able && dp[beg]>=0)return dp[beg];
else if(!able && dpf[beg]>=0)return dpf[beg];
used[beg] = true;
int sum = 0;
int maxRet = 0;
for(auto i : to[beg])
{
sum+=traversal(i, true);
}
if(!able)
{
dpf[beg] = sum;
used[beg] = false;
return sum;
}
maxRet = sum;
for(auto i : to[beg])
{
if(!used[i] && isSq(arr[beg]*arr[i]) && i != beg)
{
// int iSum = 0;
// cout<<i<<'|'<<beg<<endl;
maxRet = max(maxRet, sum+2-traversal(i, true)+traversal(i, false));
}
}
dp[beg] = maxRet;
used[beg] = false;
return maxRet;
}
int main() {
cin>>n;
// cout<<isSq(92*19)<<'!'<<endl;
to = new vector<int>[n];
arr = new int[n];
dp = new int[n];
dpf = new int[n];
red = new bool[n];
used = new bool[n];
memset(used, 0 ,sizeof(bool)*n);
memset(red, 0, sizeof(bool)*n);
for(int i = 0; i<n; ++i)
{
dp[i] = -1;
dpf[i] = -1;
}
for(int i = 0; i<n; ++i)
{
cin>>arr[i];
}
int u,v;
for(int i = 0; i<n-1; ++i)
{
cin>>u>>v;
to[u-1].push_back(v-1);
to[v-1].push_back(u-1);
}
cout<<traversal(0, true)<<endl;
}
// 64 位输出请用 printf("%lld")